题解 P2679 【子串】

hicc0305

2018-07-25 16:28:47

Solution

用f[i][j][k]表示a串匹配到i,b串匹配到j,分了k块,并且成功匹配的方案数。 当a[i]!=b[j]时,f[i][j][k]=0 当a[i]==b[j]时,f[i][j][k]=f[i-1][j-1][k]+sum(f[1][j-1][k-1],f[2][j-1][k-1]……f[i-1][j-1][k-1])。也就是不新分一个块的情况+新分一个块的情况。而对于sum,我们可以用数组进行记录,也就是每次处理完f[i][j][k],就加一下。 由于只i涉及到i和i-1,我们完全可以把这一维省掉,在处理的时候,j、k倒序枚举即可。可以解决开不下的问题。 代码: ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int mod=1e9+7; int n,m,k; int sum[210][210],f[210][210]; char a[1100],b[210]; int main() { char tmp[10]; scanf("%d%d%d",&n,&m,&k); scanf("%s%s",a+1,b+1); sum[0][0]=1; for(int i=1;i<=n;i++) for(int j=m;j>=1;j--) for(int p=k;p>=1;p--)//倒序枚举,相当于滚动数组 { if(a[i]!=b[j]) { f[j][p]=0; continue; } f[j][p]=(f[j-1][p]+sum[j-1][p-1])%mod; sum[j][p]=(f[j][p]+sum[j][p])%mod;//记录1~i的f[j][p]的方案和 } cout<<sum[m][k]; return 0; } ```