题目：https://www.luogu.org/problemnew/show/P2679
DP水题；
然而被摆了一道，下面加 // 的地方都是一开始没写好的地方...还是不周密；
仔细审题啊...连在一起的两块也可以人工看作是两块的。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int const maxn=1005,maxm=205,mod=1000000007; int n,m,K,f[3][maxm][maxm][3]; char a[maxn],b[maxm]; int rd() {int ret=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return ret*f; } int main() {n=rd(); m=rd(); K=rd();cin>>a+1; cin>>b+1;f[0][0][0][0]=1;f[1][0][0][0]=1;//!!for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=1;k<=K;k++)//从 1 开始即可 {f[i%2][j][k][0]=f[i%2][j][k][1]=0;//!f[i%2][j][k][0]=(f[(i+1)%2][j][k][0]+f[(i+1)%2][j][k][1])%mod;if(a[i]==b[j]){f[i%2][j][k][1]=(f[(i+1)%2][j-1][k-1][0]+f[(i+1)%2][j-1][k][1])%mod;(f[i%2][j][k][1]+=f[(i+1)%2][j-1][k-1][1])%=mod;//! } // else if(a[i]==b[j]) f[i%2][j][k][1]=(f[(i+1)%2][j-1][k][0])%mod; // printf("f[%d][%d][%d][0]=%d [1]=%d\n",i,j,k,f[i%2][j][k][0],f[i%2][j][k][1]); }printf("%d",(f[n%2][m][K][0]+f[n%2][m][K][1])%mod);return 0; }
