#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=1000+5,M=200+5;
const int mod=1e9+7;
char s1[N],s2[M];
int n,m,K;
int dp[2][N][M],sum[2][N][M];
//dp[i][j][k]=Σdp[i-1][j']k-1 +dp[i-1][j-1][k]
int main(){
scanf("%d%d%d%s%s",&n,&m,&K,s1+1,s2+1);
memset(dp,0,sizeof dp);
memset(sum,0,sizeof sum);
int I=0,J=1;
for (int i=1;i<=n;i++){
if (s2[1]==s1[i])
dp[0][i][1]=1;
sum[0][i][1]=sum[0][i-1][1]+dp[0][i][1];
}
for (int i=2;i<=m;i++,I^=1,J^=1){
memset(dp[J],0,sizeof dp[J]);
memset(sum[J],0,sizeof sum[J]);
for (int j=1;j<=n;j++){
if (s2[i]!=s1[j])
continue;
for (int k=1;k<=K;k++)
if (j>=2)
dp[J][j][k]=(sum[I][j-1][k-1]+dp[I][j-1][k])%mod;
else
dp[J][j][k]=dp[I][j-1][k];
}
for (int k=1;k<=K;k++)
for (int j=1;j<=n;j++)
sum[J][j][k]=(sum[J][j-1][k]+dp[J][j][k])%mod;
}
return 0;
}
拿去用吧,第一个!!!!!!!!!
@元昊选

0 条评论

目前还没有评论...

信息

ID
1413
难度
9
分类
(无)
标签
递交数
4
已通过
2
通过率
50%
上传者