【CF1015F】Bracket Substring(字符串DP)

时间:2022-12-16 23:13:03

题意:给定一个只由左右括号组成的字符串s,问长度为2*n的包含它的合法括号序列方案数,答案对1e9+7取模

1≤n≤100,1≤|s|≤200

思路:暴力预处理出s的每个前缀[0..i]后加左右括号分别能与原序列最长匹配到的位置,这一步也可以用KMP

设dp[i][j][k][l]为当前到第i位,未匹配的左括号数为j,当前最长能匹配到s的前k位,是否存在过全匹配s的方案数

有两种转移,第i+1位填左括号或者右括号

答案即为 simga dp[n<<1][0][i][1] (i=0..len(s))

学习用C++的string……

用C++的话DP的式子可以写的灵活一点,毕竟不是P,多用表达式

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 #define N   210
 7 #define oo  10000000
 8 #define MOD 1000000007
 9 
10 int dp[N][N][N][2],len[N][2],n,m;
11 string a;
12 
13 void Add(int &a,int b)
14 {
15     a+=b;
16     if(a>=MOD) a-=MOD;
17 }
18 
19 int calc(string b)
20 {
21     int len=b.size();
22     for(int i=len;i>0;i--)
23      if(a.substr(0,i)==b.substr(len-i,i)) return i;
24     return 0;
25 }
26 
27 int main()
28 {
29     int n;
30     scanf("%d",&n);
31     cin>>a;
32     int m=a.size();
33     if(a[0]=='(') len[0][0]=1;
34      else len[0][1]=1;
35     string t;
36     for(int i=0;i<=m-1;i++)
37     {
38         t+=a[i];
39         t+='(';
40         len[i+1][0]=calc(t);
41         t.pop_back();
42         t+=')';
43         len[i+1][1]=calc(t);
44         t.pop_back();
45     }
46     dp[0][0][0][0]=1;
47     for(int i=0;i<=2*n-1;i++)
48      for(int j=0;j<=n;j++)
49       for(int k=0;k<=m;k++)
50        for(int l=0;l<=1;l++)
51        {
52                if(j+1<=n) Add(dp[i+1][j+1][len[k][0]][l|len[k][0]==m],dp[i][j][k][l]);
53                if(j) Add(dp[i+1][j-1][len[k][1]][l|len[k][1]==m],dp[i][j][k][l]); 
54        }
55     int ans=0;
56     for(int i=0;i<=m;i++) Add(ans,dp[n<<1][0][i][1]);
57     printf("%d\n",ans);
58     return 0;
59 }
60