传送门
为什么前几年的
n
o
i
p
noip
n
o
i
p
总是出这种送分题啊？
这个直接线性
d
p
dp
d
p
不就完了吗？
f
[
i
]
[
j
]
[
k
]
[
0
/
1
]
f[i][j][k][0/1]
f
[
i
]
[
j
]
[
k
]
[
0
/
1
]
表示当前在第
i
i
i
个位置，已经匹配到了第
j
j
j
个位置，已经使用了
k
k
k
段，当前这个字符没用用/用了。
然后分情况简单转移一下就行了。
注意可以滚动数组优化空间。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=1005,M=205;
int n,m,K,ans=0,f[2][M][M][2],tmp=0;
char s[N],t[M];
int main(){
scanf("%d%d%d%s%s",&n,&m,&K,s+1,t+1);
f[tmp][0][0][0]=1;
for(int i=1;i<=n;++i){
tmp^=1,memset(f[tmp],0,sizeof(f[tmp])),f[tmp][0][0][0]=1;
for(int j=1;j<=m;++j){
for(int k=1;k<=K;++k){
f[tmp][j][k][0]=f[tmp^1][j][k][1]+f[tmp^1][j][k][0];
if(f[tmp][j][k][0]>=mod)f[tmp][j][k][0]-=mod;
if(s[i]==t[j]){
f[tmp][j][k][1]=f[tmp^1][j-1][k][1]+f[tmp^1][j-1][k-1][0];
if(f[tmp][j][k][1]>=mod)f[tmp][j][k][1]-=mod;
f[tmp][j][k][1]+=f[tmp^1][j-1][k-1][1];
if(f[tmp][j][k][1]>=mod)f[tmp][j][k][1]-=mod;
}
}
}
}
ans=f[tmp][m][K][1]+f[tmp][m][K][0];
if(ans>=mod)ans-=mod;
cout<<ans;
return 0;
}