2021 括号序列 · 方案二平方递推

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 2027 字

三态压成一个数组，从后往前 O(n^2) 递推

2021
区间DP

正文

// CSP-S 2021 复赛 T2 · 括号序列（方案二：单数组 O(n^2) 递推，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2021B
// 题意：同方案一（n ≤ 500，需稳过）。
// 思路（状态精简）：
//   f[l][r][0..2]：
//     0 = [l,r] 恰好是一段完整"括号单元 (X)"（可带尾星）；
//     1 = [l,r] 是合法序列（可拼接、可为纯星、可为空）；
//     2 = [l,r] 是合法序列且末尾是 (X)**…* 形式的"星尾延续"。
//   转移：
//   - f[l][r][0]：s[l]=(、s[r]=) 且 f[l+1][r-1][1]（中间任意合法）；
//   - f[l][r][2]：存在分割点 m，s[m..r] 全星（≤k 个）且
//     f[l][m-1][0]；
//   - f[l][r][1] = 纯星段(≤k) + Σ_m f[l][m][1]·f[m+1][r][0] + f[l][r][2]。
//   拼接项通过"枚举第一段端点"或前缀和优化到 O(n^2)。
// 复杂度：O(n^2)。
// 易错点：
//   1. 空串是合法序列（f[l][l-1][1] = 1，作边界）；
//   2. 尾星长度从 1 到 k，遇非星字符立即断；
//   3. 全程取模 1e9+7。
#include <cstdio>
#include <cstring>
using namespace std;

const int MOD = 1e9 + 7;
int n, k;
char s[505];
long long f[505][505][3];

bool star(int i) { return s[i] == '*' || s[i] == '?'; }

int main() {
    freopen("bracket.in", "r", stdin);
    freopen("bracket.out", "w", stdout);
    scanf("%d%d%s", &n, &k, s + 1);
    for (int l = 1; l <= n + 1; l++) f[l][l - 1][1] = 1;   // 空串
    for (int len = 1; len <= n; len++) {
        for (int l = 1, r = len; r <= n; l++, r++) {
            // 0：(X)
            if ((s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?') && r - l >= 1) {
                f[l][r][0] = f[l + 1][r - 1][1];
            }
            // 2：主体 (X) + 尾星
            for (int m = r + 1; m - r <= k && m <= n; m++) {
                if (!star(m)) break;
                f[l][m][2] = (f[l][m][2] + f[l][r][0]) % MOD;
            }
            // 1：自身来源汇总
            long long v = 0;
            if (r - l + 1 <= k) {          // 纯星段
                bool ok = true;
                for (int i = l; i <= r; i++) if (!star(i)) { ok = false; break; }
                if (ok) v = (v + 1) % MOD;
            }
            v = (v + f[l][r][2]) % MOD;
            for (int m = l; m <= r; m++) { // 拼接：左合法 × 右为单元
                v = (v + f[l][m][1] * f[m + 1][r][0]) % MOD;
            }
            f[l][r][1] = v;
        }
    }
    printf("%lld\n", f[1][n][1]);
    return 0;
}

2021 括号序列 · 方案二 平方递推

正文

CSP-S 标程 · 复赛真题的其它内容

2021 括号序列 · 方案二平方递推