蓝桥杯第12届c++A组——括号序列

题目链接

思路（来自y总）

首先这个序列中我们需要添加的是左括号和右括号， 那么显然的我们要想左括号和右括号的添加是不是相互独立的呢？答案是肯定的：

考虑到我们只能在空隙中插入括号， 如果我们添加的一对左右括号不是在同一个空隙中， 那么他们显然是互不干扰的；如果是添加在同一个空隙中， 那么他们的添加顺序是唯一的， 只能是）（， 因为如果是（）的话， 那我们本次的添加就是无效的， 不满足添加最少的括号使得序列得到匹配。 由此可得， 我们只需要单独计算出添加左括号的方案数， 乘上单独添加右括号的方案数就是答案的数量。

明确了上面那个问题，我们就可以对左右括号进行单独计算了， 我们这里以添加左括号为例。

我们如果以右括号为端点， 将整个序列进行分割， 那么在分割后的每一小段添加左括号的方案数显然只和这段序列中左括号的数量有关， 因为这段序列里全是左括号， 怎么排列都是一种。所以我们只关注左括号的个数就好了， 更准确的来说， 我们只要关注我们添加的左括号的个数。

那么我们可以设计一个状态f[i][j]表示当前枚举到第i个右括号， 我们添加了j个左括号的==合法==方案（注意， 如果我们添加的操作使得前i个右括号都被匹配完后还有剩余的左括号， 我们仍认为这个状态是合法的）， 那么我们首先预处理出每个右括号前面至少需要添加的左括号的数量记为add数组，那么显然小于add的方案都是不合法的， 对于大于add的数量， 我们将添加的左括号分为两组， 一组在第i - 1个右括号的前面， 另一组在第i - 1个括号到第i个括号之间， 那么枚举任意一段的数目就可以实现转移了

for(int i = add[1]; i <= len; i ++) f[1][i] = 1;//预处理， 很显然

for(int i = 2; i <= num; i ++)
    for(int j = add[i]; j <= len; j ++)//注意从add[i]开始， 比add[i]小的状态一定不合法
        for(int k = 0; k <= j; k ++)//k表示的是i - 1到i段添加左括号的数量
            f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;

这样我们的工作看似就完成了， 但是这个dp的时间复杂度是==n ^ 3==的， 过不了本题5k的数据， 那么我们就要考虑进行优化

我们可以明显注意到

f[i][j] = f[i - 1][0] + f[i - 1][1] + ...... + f[i - 1][j]

f[i][j + 1] = f[i - 1][0] + f[i - 1][1] + ...... + f[i - 1][j] + f[i - 1][j + 1]

那么我们可以得出

f[i][j] = f[i][j - 1] + f[i - 1][j - 1]

那么我们只需要先O(n)的算出f[i][add[i]]， 后面的f[i][j]就都可以O(1)转移出了， 总体时间复杂度==n ^ 2==， 可以通过本题

当然对与添加右括号来说， 只需要将序列镜像翻转， 然后当作匹配左括号就可以了

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int mod = 1e9 + 7;

char s[5003];
int f[5003][5003];
int add[5003];
int ans;

int Work(int len)
{
    int lcnt = 0, rcnt = 0, num = 0; // 未被匹配的左， 右括号数， 右括号编号
    memset(f, 0, sizeof(f));

    for(int i = 1; i <= len; i ++)
    {
        if(s[i] == '(')
            lcnt ++;
        else
        {
            rcnt ++;
            num ++;

            if(lcnt) rcnt --, lcnt --;

            add[num] = rcnt; // 记录最少需要添加的左括号的数量， add是单调不减的（虽然这个性质没用）
        }
    }

    for(int i = add[1]; i <= len; i ++) f[1][i] = 1;
    /* n ^ 3转移
    for(int i = 2; i <= num; i ++)
        for(int j = add[i]; j <= len; j ++)
            for(int k = 0; k <= j; k ++)
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
    */
    for(int i = 2; i <= num; i ++)
    {
        for(int j = 0; j <= add[i]; j ++) f[i][add[i]] = (f[i][add[i]] + f[i - 1][j]) % mod;

        for(int j = add[i] + 1; j <= len; j ++) f[i][j] = (f[i][j - 1] + f[i - 1][j]) % mod;
    }

    return f[num][rcnt]; //返回答案
}

int main()
{
    scanf("%s", s + 1);
    int len = strlen(s + 1);

    ans = Work(len);

    for(int i = 1; i <= len; i ++)// 镜像
        if(s[i] == '(')
            s[i] = ')';
        else
            s[i] = '(';

    std:: reverse(s + 1, s + len + 1);//翻转

    ans = 1LL * ans * Work(len) % mod;

    printf("%d\n", ans);

    return 0;
}