题目传送门:http://codevs.cn/problem/4560/
就是一个很简单的DP加一个滚动数组的优化
然而为什么纸张的我去年连这是个DP都看不出来 QAQ
#include<bits/stdc++.h> #define LL long long using namespace std; const int MOD = 1000000007; int f[2][209][209][2],w,p,n,m,K; char s1[1009],s2[1009]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ n = read(); m = read(); K = read(); scanf("%s%s",s1+1,s2+1); w = 1; f[p][0][0][0] = 1; for (int t=1;t<=n;t++,w^=1,p^=1) { memset(f[w],0,sizeof(f[w])); for (int i=0;i<=m;i++) { for (int k=0;k<=K;k++) { if (f[p][i][k][0]) { (f[w][i][k][0] += f[p][i][k][0]) %= MOD; if (s1[t] == s2[i+1]) { (f[w][i+1][k+1][1] += f[p][i][k][0]) %= MOD; } } if (f[p][i][k][1]) { (f[w][i][k][0] += f[p][i][k][1]) %= MOD; if (s1[t] == s2[i+1]) { (f[w][i+1][k][1] += f[p][i][k][1]) %= MOD; (f[w][i+1][k+1][1] += f[p][i][k][1]) %= MOD; } } } } } printf("%d\n",(f[p][m][K][0]+f[p][m][K][1])%MOD); return 0; }
哇塞,居然是沙发?留个名