以上为日照夏令营的标解（整理就贴上了）
自己对上面的理解:
状态f[i][j][k] 表示A串匹配到i B串匹配到j 用了k个子串
转移的话 f[i][j][k]=f[i-1][j-1][k]+f[i-1][j-1][k-1]分别表示i是不是建立了一个新的子串
当然这是我们会发现 这样的状态是默认了i用了 显然i可以不用 也就是说这样就遗漏了许多状态
我们重新定义一下他 加一维01表示i用了没用 f[i][j][k][0或1]
这样转移就要分开考虑01
f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]因为i没有用 所以不会有新串k不变 B串也不会更新匹配j不变
f[i][j][k][1]=
+f[i-1][j-1][k-1][0]
+f[i-1][j-1][k][1]
+f[i-1][j-1][k-1][1]
AC代码:
#include<cstdio> #define maxn 1010 #define mod 1000000007 using namespace std; int n,m,s,f[2][maxn][maxn][2],sum; char s1[maxn],s2[maxn]; int main(){ scanf("%d%d%d",&n,&m,&s); scanf("%s%s",s1+1,s2+1); for(int i=1;i<=n;i++){ f[i&1][1][1][0]=sum; if(s1[i]==s2[1]) sum++,f[i&1][1][1][1]=1; for(int j=2;j<=m;j++){ for(int k=1;k<=s;k++){ f[i&1][j][k][0]=(f[i-1&1][j][k][1]+f[i-1&1][j][k][0])%mod; if(s1[i]!=s2[j])continue; f[i&1][j][k][1]=((f[i-1&1][j-1][k-1][1]+f[i-1&1][j-1][k-1][0])%mod+f[i-1&1][j-1][k][1])%mod; } } for(int j=1;j<=m;j++){ for(int k=1;k<=s;k++){ f[i-1&1][j][k][0]=f[i-1&1][j][k][1]=0; } } } printf("%d ",(f[n&1][m][s][0]+f[n&1][m][s][1])%mod); return 0; }
以下为自己以前写的代码（感觉自己写的更优）
题解：（dp）
f(k,i,j)表示分了k段，用了第一个串中的前i个数字，已经构成了第二个串的前j个的方案数
f(k,i,j)=∑f(k−1,l,j−1) 当s1[i]==s2[j]且s1[i−1]!=s2[j−1]其中0<l<i
∑f(k−1,l,j−1)+f(k,i−1,j−1) 当s1[i]==s2[j]且s1[i−1]==s2[j−1]其中0<l<i
第一个转移是独立开辟出一个部分的可能数，第二个是算上之前就已经分了k个部分后把第k个部分扩大的方案数。还是比较好理解的，当然f数组要滚动第一维，不然会爆内存。
我觉得这一道题的难度，都和当年乌龟棋在当时的难度差不多了。但这道题的70分算法O(nm2k)比较好写，所以拉不卡差距。
相信大家在看了我的状态转移之后能想出O(nmk)的方法。其实我们需要维护的就只是那一个∑用一个tmp数组保存一下就好了（详见代码）
AC代码（int）：
#include<cstdio> using namespace std; #define N 1005 #define M 205 #define mod 1000000007 int n,m,K; int f[2][N][M]; char a[N],b[M]; int main(){ scanf("%d%d%d",&n,&m,&K); scanf("%s%s",a+1,b+1); int k=0; for(int i=0;i<=n;i++) f[0][i][0]=1; for(int h=1;h<=K;h++){ k^=1; for(int i=0;i<=n;i++) f[k][i][h-1]=0; for(int j=h;j<=m;j++){ for(int i=j;i<=n;i++){ if(a[i]==b[j]){ f[k][i][j]=((f[k][i-1][j]+f[k][i-1][j-1])%mod+f[k^1][i-1][j-1])%mod; if(i>=2) f[k][i][j]=(f[k][i][j]-f[k][i-2][j-1]+mod)%mod; } else f[k][i][j]=f[k][i-1][j]; } } } printf("%d ",f[k][n][m]); return 0; }
AC代码（long long）：
#include<cstdio> using namespace std; #define N 1005 #define M 205 #define mod 1000000007 int n,m,K; long long f[2][N][M]; char a[N],b[M]; int main(){ scanf("%d%d%d",&n,&m,&K); scanf("%s%s",a+1,b+1); int k=0; for(int i=0;i<=n;i++) f[0][i][0]=1; for(int h=1;h<=K;h++){ k^=1; for(int i=0;i<=n;i++) f[k][i][h-1]=0; for(int j=h;j<=m;j++){ for(int i=j;i<=n;i++){ if(a[i]==b[j]){ f[k][i][j]=f[k][i-1][j]+f[k][i-1][j-1]+f[k^1][i-1][j-1]; if(i>=2){ f[k][i][j]-=f[k][i-2][j-1]; if(f[k][i][j]<0) f[k][i][j]+=mod; } } else f[k][i][j]=f[k][i-1][j]; if(f[k][i][j]>=mod) f[k][i][j]%=mod; } } } printf("%lld",f[k][n][m]); return 0; }
附测试点7
ps：注意mod时不要越界
in
500 50 30 gglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbbglbbgglbbgglbbgglbbggltbgglbbgglbbgglbbgglbbgglbbgglbbgglgbgglbbgglbbgdlbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbvgglbbgglbbgglbbgglbbgglbbgglbbgglbbggllbgglbbgglbbgglbbgglbbgggbblglbbgglbbaglbbgglbbcglbbgglbbgglbbgglbbgglbbgglkbgglbbgglbbgglbbgblbbnglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgggbbgglbbgglbbgglbbgglbbgggbbgglbbgglbbgglbbgulbbgglbbgglbbgglbbgglbbgglbbgglbgglbbgglbbgglbbgglbbb gglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbb
out
941105174