链接
传送门
题意
给出一段长度为\(m\)括号序列，在它的前后添加"("和")"使得长度变为\(n\)，输出使最终序列合法的添加方式数目。
思路
定义状态\(d[i][j]\)表示长度为\(i\)，最终还需\(j\)个")"才能完全匹配的的合法序列前缀数目。可以得到状态转移公式\(d[i][j]=d[i-1][j-1]+d[i-1][j+1]\)。预处理后，枚举在原始序列前面添加的长度计算方案数目和。
代码
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
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;
const int maxn = 100000;
const int maxm = 2010;
char s[maxn];
LL d[maxm][maxm];
int main() {
d[0][0] = 1;
for (int i = 1; i < maxm; ++i) {
d[i][0] = d[i - 1][1];
for (int j = 1; j <= i; ++j) {
d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % mod;
}
}
int n, m;
scanf("%d%d%s", &n, &m, s);
int minb = 0, b = 0, len = n - m;
for (int i = 0; i < m; ++i) {
if (s[i] == '(') {
++b;
} else {
--b;
}
minb = min(minb, b);
}
LL ans = 0LL;
for (int i = 0; i <= len; ++i) {
for (int j = 0; j <= i; ++j) {
if (j >= -minb && b + j <= len && b + j >= 0) {
ans = (ans + d[i][j] * d[len - i][b + j]) % mod;
}
}
}
cout << ans << endl;
return 0;
}
|