计数类 dp 要注意重复
括号序列
思路
一来就感觉是 dp ，最开始想了个三维 $d[i, j, k]$ 表示“前 $i$ 个位置，有 $j$ 个开着的左括号， $k$ 个星号”，然后发现题目给的条件不好转移
改成区间 dp ，当然设 $d[l, r]$ 表示“ $[l, r]$ 的方案数”，然后发现 $(SA), (AS), AB$ 型转移都还要一层循环，这都可以接受，但 $ASB$ 型转移要在加两层循环，直接飙到 $O(n^4)$
大概算了一下，感觉应该是 $O(n^3)$ 的复杂度，那么重点解决 $ASB$ 型转移，直接再记一个 $f[l, r]$ 表示 $SA$ 型的方案数（顺便就再记一个 $g[l, r]$ 表示 $AS$ 型），然后时间直接变成 $O(n^3)$ ，一跑样例二，多了
大概感觉是算重了，仔细看了许久，发现 $AB$ 型如果直接由 $d[l, k] * d[k + 1, r] \to d[l, r]$ ，那么 $AAAA$ 这样的东西就有 $A + AAA, AA + AA, AAA + A$ 三种分解本质相同，发现 $(X)$ （ $X$ 是某种使得 $(X)$ 是满足条件的 $A$ 型字符串）是不会有更多的分解的，换言之，它是“最小的”，所以直接记 $h[l, r]$ 为 $(X)$ 的方案，然后由 $h[l, k] * d[k + 1, r] \to d[l, r]$ ，再跑，发现还是多了
一直没想出来那里重，方案数又太多不是很好调，就开始乱搞：大概输出了点东西确定自己没犯 sb 错误，那么只能是 dp 有锅；尝试把几种不同类型的转移去掉看答案变少了多少，发现样例二根本没有 $(AS)$ 型的贡献，大胆猜 $(SA), (AS)$ 都是对的，感觉 $(A), (S)$ 不易错，就尝试把 $ASB$ 型的 $d[l, k] * f[k + 1, r] \to d[l, r]$ 改成 $h[l, k] * f[k + 1, r] \to d[l, r]$ ，发现对了！直接过了所有样例，一交 AC 了
然后思考为啥：我以为 $ASB$ 不会重是因为我觉得枚举的是 $\mid A \mid$ ，长度不同当然是不同的分解，因为有 $S$ 隔开，但我就没有想到 $ASB$ 是不会和 $ASB$ 重，但对于 $CASB$ 这个串，它在 $C + ASB$ 这个 $AB$ 型分解统计了一次，在 $CA + S + B$ 这个 $ASB$ 型分解也统计了一次，所以重了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
using LL = long long;
const int N = 500 + 50, P = 1e9 + 7;
int n, num;
int d[N][N], f[N][N], g[N][N], h[N][N];
bool is[N][N];
char s[N];
void adj(int &x){ x += (x >> 31) & P; }
int main()
{
scanf("%d %d %s", &n, &num, s + 1);
for (int i = 1; i <= n; ++i) if (s[i] == '*' || s[i] == '?')
{
is[i][i] = true;
for (int j = i + 1; j <= n && j - i + 1 <= num; ++j)
if (s[j] == '*' || s[j] == '?') is[i][j] = true;
else break;
}
for (int i = 1; i < n; ++i) if ((s[i] == '(' || s[i] == '?') && (s[i + 1] == ')' || s[i + 1] == '?')) d[i][i + 1] = h[i][i + 1] = 1;
for (int len = 3; len <= n; ++len)
for (int l = 1, r = l + len - 1; r <= n; ++l, ++r)
{
if ((s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?'))
{
adj(h[l][r] += d[l + 1][r - 1] - P);
if (is[l + 1][r - 1]) adj(h[l][r] += 1 - P);
adj(h[l][r] += f[l + 1][r - 1] - P);
adj(h[l][r] += g[l + 1][r - 1] - P);
adj(d[l][r] += h[l][r] - P);
for (int k = l + 1; k < r - 1; ++k) adj(d[l][r] += LL(h[l][k]) * d[k + 1][r] % P - P);
for (int k = l + 1; k < r - 1; ++k) adj(d[l][r] += LL(h[l][k]) * f[k + 1][r] % P - P);
}
if ((s[r] == ')' || s[r] == '?'))
for (int k = l; k < r - 1; ++k)
if (is[l][k]) adj(f[l][r] += d[k + 1][r] - P);
else break;
if ((s[l] == '(' || s[l] == '?'))
for (int k = r; k > l + 1; --k)
if (is[k][r]) adj(g[l][r] += d[l][k - 1] - P);
else break;
}
printf("%d\n", d[1][n]);
return 0;
}
|