题解 P2679 【子串】

2018-07-25 16:28:47


用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倒序枚举即可。可以解决开不下的问题。

代码:

#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;
}