CF1015F Bracket Substring (KMP+DP)

题目大意：给你一个长度为$n$的括号序列$T$，要求你构造一个长度为$2n$的括号序列$S$，保证这个括号序列在插入数字后一定是正确的，并且$T$是$S$的一个子串

还以为是什么纯粹的数学构造题，一通乱搞无果。好吧，并没有想到$KMP$....

题解：首先用$KMP$预处理出数组$to[i][0/1]$，表示在$i+1$位填上括号$'('$和$')'$后匹配到字符串T的位置

定义$f[i][j][k][0/1]$表示已经添加了$i$个括号，左右括号数量之差是$j$，已经匹配到了字符串$T$的第$k$位，是否包含$T$串

再用$DP$转移即可，实现很简单

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 205

 #define maxn 250

 #define uint unsigned int

 #define ll long long

 #define mod 1000000007

 using namespace std;

 int n,len;

 char str[N];

 uint f[N][N][N][];

 int nxt[N],to[N][];

 void get_nxt()

 {

     int i=,j=;nxt[]=;

     while(i<=len){

         if(j==||str[i]==str[j]){

             i++,j++;nxt[i]=j;

         }else{j=nxt[j];}

     }

     for(int i=,k;i<len;i++)

     {

         k=i;

         if(str[i+]=='('){

             to[i][]=k+;k=k+;

             for(;str[k]!=')'&&k;k=nxt[k]);

             to[i][]=k;

         }else{

             to[i][]=k+;k=k+;

             for(;str[k]!='('&&k;k=nxt[k]);

             to[i][]=k;

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

     scanf("%s",str+);

     len=strlen(str+);

     get_nxt();

     f[][][][]=;

     for(int i=;i<*n;i++)

     {

         for(int j=;j<=n;j++){

             for(int k=;k<len;k++)

             {

                 if(j<n)(f[i+][j+][to[k][]][to[k][]==len]+=f[i][j][k][])%=mod; //'('

                 if(j>)(f[i+][j-][to[k][]][to[k][]==len]+=f[i][j][k][])%=mod; //')'

             }

             if(j<n)(f[i+][j+][len][]+=f[i][j][len][])%=mod;

             if(j>)(f[i+][j-][len][]+=f[i][j][len][])%=mod;

         }

     }

     int num=;

     printf("%u\n",f[*n][][len][]);

     return ;

 }

巴特西

CF1015F Bracket Substring (KMP+DP)

最新文章

热门文章