原题网址：http://www.lydsy.com/JudgeOnline/problem.php?id=3484 题意： 我们把一种由[、]、(、)组成的序列成为合法的： 单独的“()”和“[]”是合法的。 如果A和B是合法的，那么AB也是合法的。 如果A是合法的，那么(A)和[A]也是合法的。 有一个序列A，他的所有的“[”和“]”都被替换成了“(”，这样形成了序列B，现在已知序列B，求有多少种可能的序列A，答案mod 10^9+9。 2≤N≤30000 题解：一开始YY了一个组合数的方法，先算小括号的方案数再乘上卡特兰数，但是小括号的位置是会影响中括号的，结果WA了。结果被AK龙指点一发，在原序列中选一些左括号变成右括号是和题意序列一一对应的，就变成dp了…… f[i][j] 表示前 i 个和为 j 的方案数，再卡卡常。
#include<bits/stdc++.h> const int N = 30050; const int P = 1e9 + 9; int n, f[2][N], m[N]; char ch[N]; int main() { scanf("%d", &n); scanf("%s", ch + 1); if (n & 1 || ch[1] == ')') {printf("0\n"); return 0;} for (int i=n - 1; i > 0; i--) m[i] = std::min(n - i, i); int now = 0, last = 1; f[1][1] = 1; for (int i=2; i <= n; i++, now^=1, last^=1) { if (f[last][0] > P) f[last][0] -= P; for (int j=1; j <= m[i] + 1; j++) { if (f[last][j] > P) f[last][j] -= P; f[now][j - 1] = f[last][j]; } if (ch[i] == '(') for (int j=0; j <= m[i]; j++) f[now][j + 1] += f[last][j]; } printf("%d\n", f[last][0] % P); return 0; }