\(\rm P7914\) [CSP 2021] 括号序列 加深理解

做题简记。

这里觉得第一篇题解的做法是最优秀的，因为这才是真正的dp强调的不重不漏。

这个做法只设了一个dp数组，应该跟其他设两个之类的解法是共通的。

解法

观察

结合数据范围，我们确定这是一道区间dp题。先设出 \(f[l, r]\) 的基本状态，然后观察如何转移。

仔细观察一个复杂的合法序列是怎么被一步一步拼接起来的。具体的，有：

• S \(\to\) (S)
• S + A \(\to\) (SA)
• A + S \(\to\) (AS)
• A + B \(\to\) AB
• A + S + B \(\to\) ASB

那么略加思考我们会发现这题其实很容易算重。那么为了解决这个问题，我们就不能无脑合并了，而是要变换一下传统的转移方式。考虑将 ***（单个*串，记为 X）和 (...)（左右括号匹配的合法串，记为 Y，例如((*)*())，但不包含 ()**()*()）作为一个长括号串的“零件”，一步步从左往右拼接。

那么在将 X 和 Y 拼接的过程中就涉及到很多转移的中间状态，具体的有：

• A (...)*(...)*（最右端是*）
• B *(...)*(...)（最左端是*）
• C (...)*(...)（合法串）
• D *(...)*(...)*（左右都是*）

那么在草稿纸上写写画画，我们不难得到这四种中间状态（以及 Y）的转化关系：

（原串 + 零件 = 新串）

直接拼接 \(6\) 种：

• A + Y = C
• B + X = D
• B + Y = B
• C + X = A
• C + Y = C
• D + Y = B

套括号 \(3\) 种：

• (A) = Y
• (B) = Y
• (C) = Y

观察到 *** 和 (...) 在参与拼接的时候都是作为极长的零件，而且默认是从左往右拼接，那么就不存在算重（比如说 ()()() = () + ()() = ()() + () ）的问题了。

设计状态

有了以上的分析，我们可以写出最终状态及转移方程（参照了原题解）：

• 设 \(f[l, r, 0]\) 表示 \(s[l, r]\) 内 *** 的拼法个数。
• 设 \(f[l, r, 1]\) 表示 \(s[l, r]\) 内 (...) 的拼法个数。
• 设 \(f[l, r, 2]\) 表示 \(s[l, r]\) 内 A 的拼法个数。
• 设 \(f[l, r, 3]\) 表示 \(s[l, r]\) 内 C 的拼法个数。（包含了(...) 的情况，相当于“广义”）
• 设 \(f[l, r, 4]\) 表示 \(s[l, r]\) 内 B 的拼法个数。
• 设 \(f[l, r, 5]\) 表示 \(s[l, r]\) 内 D 的拼法个数。（包含了*** 的情况，相当于“广义”）

转移方程

转移如下：

• X: \(f[l, r, 0]\) 直接特判。

• Y: \(f[l, r, 1] = \text{valid}(l, r)\times (f[l, r, 0] + f[l, r, 2] + f[l, r, 3] + f[l, r, 4])\) ，即 (A) = Y, (B) = Y, (C) = Y。

\(\rm valid\) 表示 \(s[l]\) 和 \(s[r]\) 能不能配成 ( 和 )。

• A: \(f[l, r, 2] = \sum_i f[l, i, 3]\times f[i + 1, r, 0]\) ，即 C + X = A。

• C: \(f[l, r, 3] = f[l, r, 1] + \sum_i (f[l, i, 2] + f[l, i, 3])\times f[i + 1, r, 1]\)，即 A + Y = C, C + Y = C。

• B: \(f[l, r, 4] = \sum_i (f[l, i, 4] + f[l, i, 5])\times f[i + 1, r, 1]\)，即 B + Y = B, D + Y = B。

• D: \(f[l, r, 5] = f[l, r, 0] + \sum_i f[l, i, 4]\times f[i + 1, r, 0]\)，即 B + X = D。

一些细节：

如何理解“广义”？就是说将这些特殊的串放到上面一般的转移中也是合法的，故也要算进答案。

为了方便 \(f[l, r, 0]\) 的特判，我们令 \(f[i, i - 1, 0] = 1\)，具体见代码。

最终答案为 \(f[1, n, 3]\)（C 串）。

Code

用记忆化搜索实现的代码：

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

char s[N];
int n, k, vis[N][N];
LL f[N][N][6];

inline auto &dp(int l, int r, int i) { return f[l][r][i]; }
inline int valid(int l, int r) { return (s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?'); }

void dfs(int l, int r) {
    if(l > r) return;
    if(vis[l][r]) return;
    for(int i = l; i < r; ++i) dfs(l, i), dfs(i + 1, r);
    if(r - l + 1 <= k) dp(l, r, 0) = dp(l, r - 1, 0) && (s[r] == '*' || s[r] == '?');
    vis[l][r] = 1;
    if(r - l < 1) goto ED;
    if(valid(l, r)) 
        (dp(l, r, 1) += dp(l + 1, r - 1, 0) + dp(l + 1, r - 1, 2) + 
                        dp(l + 1, r - 1, 3) + dp(l + 1, r - 1, 4)) %= mod;
    for(int i = l; i < r; ++i) {
        (dp(l, r, 2) += dp(l, i, 3) * dp(i + 1, r, 0)) %= mod;
        (dp(l, r, 3) += (dp(l, i, 2) + dp(l, i, 3)) * dp(i + 1, r, 1)) %= mod;
        (dp(l, r, 4) += (dp(l, i, 4) + dp(l, i, 5)) * dp(i + 1, r, 1)) %= mod;
        (dp(l, r, 5) += dp(l, i, 4) * dp(i + 1, r, 0)) %= mod;
    }
    ED:
    (dp(l, r, 5) += dp(l, r, 0)) %= mod;
    (dp(l, r, 3) += dp(l, r, 1)) %= mod;
}

signed main() {
    scanf("%d %d\n%s", &n, &k, s + 1);
    for(int i = 1; i <= n; ++i) dp(i, i - 1, 0) = 1;
    dfs(1, n);
    printf("%lld", dp(1, n, 3));
    return 0;
}