[CSP-S 2021] 括号序列题解

OMG_wc · 2021-11-01 13:17:11 · 题解

题目中把超级括号序列分成了三类：

• 第一类()和(S)
• 第二类AB和ASB
• 第三类(SA)、(AS)、(A)

显然这是一道区间DP题，我们就根据这三种构成方式来转移。

首先定义f[i][j][0/1]表示 [i,j] 这个区间的合法超括序列数，最后一维表示 s_i 和 s_j 是否是匹配的括号对。之所以这样定义，是因为在计算第二类是时，为了避免重复计算，要枚举哪个右括号和 s_i 是匹配的，这样拆分出第一个括号来转移就不会重复。

那么f[i][j][0]是从第二类转移过来的，而f[i][j][1]是从第一类和第三类转移过来的。

• 第一类其实就是唯一的情况，判断一下区间长度是否小于等于 m+2 即可。

• 第三类 (A) 的情况就直接从f[i+1][j-1][0]+f[i+1][j-1][1]转移；

  (SA)就枚举一个 k 表示 [i+1,k] 全是*，[k+1,j-1] 是另外一个合法的超括序列，从f[k + 1][j - 1][0] + f[k + 1][j - 1][1]转移；

  (AS)同理。

• 第二类需要把 [i,j] 这个区间分成三段：[i,k]是第一对超括，[k+1,z-1] 都是* （z=k+1 就表示不存在这段），[z,j] 是后面的合法超括序列，转移就是f[i][k][1]*(f[z][j][0]+f[z][j][1])。

  如果朴素枚举 k 和 z 会导致时间复杂度为 O(n^4) ，见下面代码：

for (int k = i + 1; k < j; k++) {
    // s[i]和s[k]匹配
    if (s[k] == ')' || s[k] == '?') {
        LL t = 0;
        //[k+1,z-1] 全为*   [z,j] 为合法超级括号
        for (int z = k + 1; z <= j && z - 1 - k <= m; z++) {
            if (s[z] == '(' || s[z] == '?')
                t += f[z][j][0] + f[z][j][1];
            if (s[z] != '*' && s[z] != '?') break;
        }
        t %= mod;
        f[i][j][0] += f[i][k][1] * t % mod;
    }
}

显然代码中 t 的计算不需要枚举，可以进行一个后缀和优化。首先预处理b[i]表示从 1 开始*最多能持续到的位置，然后维护g[j][i] 表示所有f[k][j][0/1]的和，这样只需枚举一个 k，然后所需的一段区间和就通过两个后缀和相减得出。

总时间复杂度 O(n^3) ，代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 505;

int n, m;
char s[N];
LL f[N][N][2];  //0/1 表示左右边界是否匹配
LL g[N][N];     //g[j][i] 表示 所有f[k][j][0/1]的和
int b[N];       // b[i] 表示从i开始*最多能持续到的位置
int main() {
    scanf("%d%d%s", &n, &m, s + 1);
    b[n + 1] = n;
    for (int i = n; i >= 1; i--) {
        if (s[i] == '*' || s[i] == '?')
            b[i] = min(b[i + 1], i + m - 1);
        else
            b[i] = i - 1;
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 1, j = i + len - 1; j <= n; i++, j++) {
            if (s[i] != '(' && s[i] != '?' || s[j] != ')' && s[j] != '?') {
                g[j][i] = g[j][i + 1];
                continue;
            }
            if (len - 2 <= m) {
                f[i][j][1] = 1;
                for (int k = i + 1; k < j; k++) {
                    if (s[k] != '*' && s[k] != '?') f[i][j][1] = 0;
                }
            }
            // (A)
            f[i][j][1] += f[i + 1][j - 1][0] + f[i + 1][j - 1][1];
            // (SA)
            for (int k = i + 1; k <= j - 1 && k - i <= m; k++) {
                if (s[k] != '*' && s[k] != '?') break;
                f[i][j][1] += f[k + 1][j - 1][0] + f[k + 1][j - 1][1];
            }
            // (AS)
            for (int k = j - 1; k >= i + 1 && j - k <= m; k--) {
                if (s[k] != '*' && s[k] != '?') break;
                f[i][j][1] += f[i + 1][k - 1][0] + f[i + 1][k - 1][1];
            }
            // ASB
            for (int k = i + 1; k < j; k++) {
                // s[i]和s[k]匹配
                if (s[k] == ')' || s[k] == '?') {
                    f[i][j][0] += f[i][k][1] * (g[j][k + 1] - g[j][min(j, b[k + 1] + 2)] + mod) % mod;
                }
            }
            f[i][j][0] %= mod;
            f[i][j][1] %= mod;
            g[j][i] = (g[j][i + 1] + f[i][j][0] + f[i][j][1]) % mod;
        }
    }
    printf("%lld\n", (f[1][n][0] + f[1][n][1]) % mod);
    return 0;
}