蓝桥杯-括号序列

104 阅读 0 评论 69 点赞

我是靠谱客的博主冷艳火车，这篇文章主要介绍蓝桥杯-括号序列，现在分享给大家，希望可以做个参考。

题目描述
给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，
会产生不同的添加结果，请问有多少种本质不同的添加结果。

两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。

例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：
()()()、()(())、(())()、(()()) 和 ((()))。

输入描述
输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。

输出描述
输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007(即 10^9 + 7)的余数。

输入输出样例
示例 1
输入
((()

输出
5

求添加括号的方案数，可能出现三种情况：

1.需要添加左括号（）））
2.需要添加右括号（（（）
3.需要添加左括号和右括号））（（
其中，情况1和情况2 是对称的，所以要求情况2，可以将字符串进行镜像对称，
然后用情况1的代码来解决，而情况3是情况1和情况2相乘的结果。

接下来，讨论情况1如何处理：
f[i][j]表示在第i个右括号前添加j个左括号的方案数，
前提条件为 j>=i-sum[i](sum[i]为原序列第i个右括号前的左括号数)
转移方程： f[i][j] = f[i-1][0]+f[i-1][1]+...+f[i-1][j]

最后，如果字符串有n个右括号，需要添加的左括号数为cnt1,那么f[n][cnt1]就是在第n个右括号前添加cnt1个左括号的方案数。

本题需要定义的变量如下：

复制代码

1
2
3
4
5
6
7
8
const long M = 1e9 + 7;
string s;         //读入括号序列
long sum[5001];  //sum[i]为原序列第i个右括号前的左括号数
long cnt1 = 0;    //需要添加cnt1个左括号
long cnt2 = 0;    //需要添加cnt2个右括号
long n = 0;     //右括号的个数
long f[5001][5001];  //f[i][j]表示在第i个右括号前添加j个左括号的方案数
long ne[5001];    //ne[j]表示f[i-1][0]+f[i-1][1]+....+f[i-1][j]的和

统计右括号的个数、需要添加的左括号个数、需要添加的右括号的个数、第i个右括号前有多少个左括号的代码如下;

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
memset(sum, 0, sizeof(sum));
j = 1;
    for (i = 0; i < s.length(); ++i)
    {
        if (s[i] == '(')   //进栈
        {
            cnt2++;
            sum[j]++;
        }
        else
        {
            n++;
            j++;
            if (cnt2 == 0)
                cnt1++;
            else
                cnt2--;
        }
    }
    for (i = 1; i < j; ++i)
        sum[i] += sum[i - 1];

求f[n][cnt1]的代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
long i, j, k;
    memset(f, 0, sizeof(f));
    //初始化
    for (i = 1; i <= cnt1; ++i)
        f[1][i] = 1;    //在第1个右括号前无论添加多少个左括号的方案数均为1
    if (sum[1] > 0)
        f[1][0] = 1;
    for (i = 2; i <= n; ++i)  //将下面注释掉的三层for循环改成两层for循环，提高效率
    {
        ne[0] = f[i - 1][0];
        for (k = 1; k <= cnt1; ++k)
            ne[k] = (ne[k - 1] + f[i - 1][k]) % M;
        for (j = max((long)0, i - sum[i]); j <= cnt1; ++j)
            f[i][j] += ne[j];
    }
  /*  for (i = 2; i <= n; ++i)
    {
        for (j = max((long)0, i - sum[i]); j <= cnt1; ++j)
        {
            for (k = 0; k <= j; ++k)
                f[i][j] = (f[i][j] + f[i - 1][k]) % M;
        }
    }*/

    return f[n][cnt1];

有了这三段代码就可以求出在第n个右括号前添加cnt1个左括号的方案数了，若还需要求在第n个左括号后添加cnt2个右括号的方案数，只需要把字符串进行镜像对称，然后再统计右括号的个数、需要添加的左括号个数、需要添加的右括号的个数、第i个右括号前有多少个左括号，就可以将添加右括号改成添加左括号，然后用上面的添加左括号的代码即可。