loj2424 「NOIP2015」子串[字符串DP]

给定字符串 A，B，要求从 A 中取出互不重叠的 k 个非空子串，按照出现顺序拼起来后等于 B。求方案数。n ≤ 1000,m ≤ 200。

主要是状态的转移。先设计出$f_{i,j,k}$表长度$B_j$分了$k$段很好想，但是发现并不容易转移。

主要瓶颈在于当枚举了状态$f_{i,j,k}$ 的时候加入可以匹配（$A_i=B_j$），怎么从前面$A_1\sim A_{i-1}$里找出$k-1$块的$j-1$的方案数。（注意下面几行都是基于当前$A_i=B_j$这个条件的）

发现这个是可以叠加的，也就是$f_{i,j,k}$可以继承$f_{i-1,j,k}$的所有方案，那么只要不断继承，像滚雪球一样，求$f_{i,j,k}$直接就从$f{i-1,j-1,k-1}$来推就好了。

第二个问题是，怎么处理拼接。如果枚举一段子串去匹配显然不太可做，发现拼接过程实际就是强制$i-1$处被选入了$k$个块内，然后和$i$位一合并，就完成了拼接。

于是，为了知道$i-1$强制被选了的情况下有多少种$k$个块的方案，故再添加一维$0/1$表示是否被选。

这下就可以推了。

具体可以参见代码（我用了顺推格式）。注意滚动。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define dbg(x) cerr << #x << " = " << x <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=+,M=+,P=1e9+;

 int f[][M][M][],now;

 int n,m,l;

 char s[N],t[M];

 inline void add(int&A,int B){A+=B;A>=P&&(A-=P);}

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     read(n),read(m),read(l);

     scanf("%s",s+),scanf("%s",t+);

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

     for(register int i=;i<n;++i,now^=){

         for(register int j=;j<=m;++j){

             for(register int k=;k<=l;++k){

                 add(f[now^][j][k][],f[now][j][k][]),add(f[now^][j][k][],f[now][j][k][]);

                 if(s[i+]==t[j+])

                     add(f[now^][j+][k+][],f[now][j][k][]),

                     add(f[now^][j+][k+][],f[now][j][k][]),

                     add(f[now^][j+][k][],f[now][j][k][]);

             //    printf("%d %d %d %d %d\n",i,j,k,f[now][j][k][0],f[now][j][k][1]);

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

             }

         }

     }

     printf("%d\n",(f[now][m][l][]+f[now][m][l][])%P);

     return ;

 }

思路总结：1.继承方案，方便统计。2.子串问题中拼接可以设计0/1状态表示末尾有没有被选，这样可以直接和后面的东西合并

巴特西

loj2424 「NOIP2015」子串[字符串DP]

最新文章

热门文章