2021 括号序列 · 方案一立方区间 DP

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

给定含 ( ) * ? 的串（? 可替为任一字符），构造长度

2021
区间DP

正文

// CSP-S 2021 复赛 T2 · 括号序列（方案一：O(n^3) 区间 DP）
// 原题：https://oj.yecheng.tv/p/CSPS2021B
// 题意：给定含 ( ) * ? 的串（? 可替为任一字符），构造长度恰为 n、
//       恰有 k 对括号、没有任何 ***/… 超长星段（连续 * 个数 < k+1）
//       的合法"括号序列"（定义：S = 空串 / AAA / (A) / (A)**…* 等
//       拼接形式，括号恰好 k 对）。求方案数 mod 1e9+7。
// 思路（区间 DP）：
//   f[l][r][t]：区间 [l,r] 构成"形式 t"的方案数。为清晰，方案一用
//   两个数组：g[l][r] = [l,r] 是"完整括号对包裹段 (X)"的方案数；
//   f[l][r] = [l,r] 是合法序列（拼接/包裹/纯星）的方案数。转移：
//   - 纯星段：全为 * 且长度 ≤ k → 方案数 1；
//   - 包裹：s[l] = (、s[r] = )，中间 X 合法（含"星尾"）：g[l][r] =
//     Σ f[l+1][r-1] 的所有合法子形态（含尾部星）；
//   - 拼接：f[l][r] = Σ f[l][m] · f[m+1][r]。
//   n ≤ 500，三重循环 O(n^3) = 1.25e8 可过。
// 复杂度：O(n^3)。
// 易错点：
//   1. 尾部星的处理：(A)*** 这种形态括号对内部合法 + 外部纯星；
//   2. 连续 * 个数上限是 k（不是 k+1）；
//   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];                 // 合法序列
long long g[505][505];                 // (X) 完整包裹

bool allStar(int l, int r) {
    for (int i = l; i <= r; i++)
        if (s[i] != '*' && s[i] != '?') return false;
    return true;
}

int main() {
    freopen("bracket.in", "r", stdin);
    freopen("bracket.out", "w", stdout);
    scanf("%d%d%s", &n, &k, s + 1);
    // 长度 1..k 的纯星段
    for (int l = 1; l <= n; l++) {
        for (int len = 0; len <= k && l + len <= n; len++) {
            if (allStar(l, l + len)) f[l][l + len] = 1;
        }
    }
    for (int len = 2; len <= n; len++) {
        for (int l = 1, r = len; r <= n; l++, r++) {
            // 包裹：(X) —— 中间为任意合法序列（含空）
            if ((s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?')) {
                g[l][r] = f[l + 1][r - 1];
                f[l][r] = (f[l][r] + g[l][r]) % MOD;
            }
            // 拼接：f[l][r] = Σ f[l][m] · f[m+1][r]
            for (int m = l; m < r; m++) {
                f[l][r] = (f[l][r] + f[l][m] * f[m + 1][r]) % MOD;
            }
            // 尾部星段：f[l][r] 由 g[l][m] + 星段 组成
            for (int m = l + 1; m <= r; m++) {
                // f[l][r] += g[l][m-1] * star(m, r)（m..r 全星，长度 ≤ k）
                if (r - m + 1 <= k && allStar(m, r)) {
                    f[l][r] = (f[l][r] + g[l][m - 1]) % MOD;
                }
            }
        }
    }
    printf("%lld\n", f[1][n]);
    return 0;
}

2021 括号序列 · 方案一 立方区间 DP

正文

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

2021 括号序列 · 方案一立方区间 DP