【NOIP2015】 Day2 T2 字串（多维动归）

2018-09-12

原题传送门（洛谷）https://www.luogu.org/problemnew/show/P2679

模拟考试的时候完全没有想到正确的DP方程呢

本来写了一个大致是对的转移方程结果算了一下空间大概不够就放弃了（第一维可以滚动掉的啊喂傻孩子啊）愣是写了50分暴力

下面是五十分的原代码

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #define For(i,a,b) for(register int i=a;i<=b;++i)

 #define Dwn(i,a,b) for(register int i=a;i>=b;--i)

 #define Re register

 using namespace std;

 const int md=1e9+;

 int na,nb,kx;

 string As,Bs;

 int sum=;

 char c[];

 int cf[];

 int main(){

 //    freopen("ex2.in","r",stdin);

     freopen("substring.in","r",stdin);

     freopen("substring.out","w",stdout);

     cin>>na>>nb>>kx;

     cin>>As; cin>>Bs;

     if(kx==){

         int px=;

         while(){

             int p=As.find(Bs,px);

             if(p==-)break;

             sum++; px=p+;

             if(sum>=md)sum%=md;

         }

         cout<<sum%md<<endl; return ;

     }

     if(kx==){

         string s1,s2;

         For(i,,nb-){

             s1=""; s2="";

             For(j,,i)s1=s1+Bs[j];

             For(j,i+,nb-)s2=s2+Bs[j];

         //    cout<<s1<<" "<<s2<<" "<<sum<<endl;

             int px1,px2;

             int sum2=;

             px1=px2=;

             while(){

                 int p1=As.find(s1,px1);

                 if(p1==-)break;

                 sum2=;

                 px2=p1+s1.size();

                 if(p1>na-)break;

                 while(){

                     int p2=As.find(s2,px2);

                     if(p2==-)break;

                     sum2++; px2=p2+;

                     if(sum2>=md)sum2%=md;

                 }

                 sum+=sum2;    if(sum>=md)sum%=md;

                 px1=p1+;

             }

         }

         cout<<sum%md<<endl;

         return ;

     }

     if(kx==nb){

         For(i,,nb-)c[i+]=Bs[i],cf[i+]=;

         For(i,,na-){

             char ac=As[i];

             Dwn(j,nb,){

                 if(ac==c[j]){

                     if(j==)cf[j]++;

                     else cf[j]+=cf[j-];

                     cf[j]%=md;

                 }

             }

         }

         sum=cf[nb]%md;

         cout<<sum<<endl;

         return ;

     }

 }

当k=1，（即只能分一个字串）直接s.find()去搜就好了

当k=2，（即分两个字串）还是暴力用find()去搜

然后当k=m (即与B串等长）想了一个挺巧妙的方法。。用 cf[i] 数组表示此时的B串前 i 位的方案数按顺序考虑 A串的一个字符

从后往前枚举 i 当 A[j]== B[i] cf[i]+=cf[i-1] (算了算了都是暴力不看也罢

正确方法

多维动归！

用我们奥赛教练的话来说就是

每次只要一考到多维动归我就替学生捏一把汗这道题是能否拿到绝对高分的关键！！

然鹅模拟测试时我没做出来呢

好了下面正经写题解

DP数组 f[i][j][k][0/1] 表示A的前i位 B的前j位用了k个字串 A的第i个字串是否使用的方案数

那么我们很容易就可以得到转移方程

A[i]==B[j]

1. 不取（0）f[i][j][k][0] <-- f[i-1][j][k][0] + f[i-1][j][k][1]

2. 取（1）f[i][j][k][1] <-- f[i-1][j-1][k][1] (与前方字符连成一个字串）+ f[i-1][j-1][k-1][1](自己单独另起一串）+ f[i-1][j-1][k-1][0]

A[i]!=B[j]

1. 不取（0）f[i][j][k][0] <-- f[i-1][j][k][0] + f[i-1][j][k][1]

2. 取显然只能等于 0

初始边界所有的 f[i][0][0][0]=1

然后愉快地把第一维 i 用滚动数组滚掉即可

复杂度 O(nmk)

附上代码

 // luogu-judger-enable-o2

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #define For(i,a,b) for(register int i=a;i<=b;++i)

 #define Re register

 using namespace std;

 const int Na=1e3+,Nb=;

 const int md=1e9+;

 long long f[][Nb][Nb][];

 char A[Na],B[Nb];

 int na,nb,kx;

 int main(){

 //    freopen("substring9.in","r",stdin);

 //    freopen("substring.out","w",stdout);

     scanf("%d%d%d",&na,&nb,&kx);

     scanf("%s",A+); scanf("%s",B+);

     f[][][][]=f[][][][]=;

     For(i,,na){

         int now=i%;

         For(j,,nb) For(k,,kx){

             if(A[i]==B[j]){

                 f[now][j][k][]=(f[now^][j-][k][]+f[now^][j-][k-][]+f[now^][j-][k-][])%md;

                 f[now][j][k][]=(f[now^][j][k][]+f[now^][j][k][])%md;

             }else{

                 f[now][j][k][]=;

                 f[now][j][k][]=(f[now^][j][k][]+f[now^][j][k][])%md;

             }

         }

     }

     long long fn=f[na%][nb][kx][]+f[na%][nb][kx][];

     cout<<fn%md<<endl;

     fclose(stdin); fclose(stdout);

     return ;

 }

巴特西

【NOIP2015】 Day2 T2 字串（多维动归）

最新文章

热门文章

巴特西

【NOIP2015】 Day2 T2 字串 （多维动归）

最新文章

热门文章

【NOIP2015】 Day2 T2 字串（多维动归）