题解 P2679 【子串】
hicc0305
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倒序枚举即可。可以解决开不下的问题。
代码:
```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;
}
```