Codeforces Round #501 (Div. 3) F. Bracket Substring

时间:2024-01-16 10:49:08

题目链接

Codeforces Round #501 (Div. 3) F. Bracket Substring

题解

官方题解

http://codeforces.com/blog/entry/60949 ....看不懂

设dp[i][j][l]表示前i位,左括号-右括号=j,匹配到l了

状态转移,枚举下一个要填的括号,用next数组求状态的l,分别转移

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 207;
const int mod = 1e9 + 7;
char s[maxn];
int next[maxn],dp[maxn][maxn][maxn],n;
void GetNext(int l) {
next[0] = 0;
for(int i = 1; i <= l; i++) {
int p = next[i-1];
while(p > 0 && s[p] != s[i]) p = next[p-1];
next[i] = p + 1;
}
}
int main() {
scanf("%d%s",&n,s + 1);
int len = strlen(s + 1);
GetNext(len);
dp[0][0][0] = 1;
for(int i = 0;i <= 2 * n;++ i)
for(int j = 0;j <= n; ++ j) {
for(int l = 0;l < len;++ l) {
int x = l + 1;
while(x > 0 && s[x] != '(') x = next[x - 1];
dp[i + 1][j + 1][x] = (dp[i + 1][j + 1][x] + dp[i][j][l]) % mod;
x = l + 1;
while(x > 0 && s[x] != ')') x = next[x - 1];
if(j > 0)
dp[i + 1][j - 1][x] = (dp[i + 1][j - 1][x] + dp[i][j][l]) % mod;
}
dp[i + 1][j + 1][len] =(dp[i + 1][j + 1][len] + dp[i][j][len]) % mod;
if(j > 0) dp[i + 1][j - 1][len] = (dp[i][j][len] + dp[i + 1][j - 1][len]) % mod;
}
cout << dp[2 * n][0][len] << endl;
return 0;
}