题目：https://www.luogu.org/problemnew/show/P2679
一看就是因为最后一位选不选对于总共有几个子串有影响，所以0/1记录一下末位选没选。
！就算和上一个子串相连，也可以人为看成两个子串！（认真读提示）
注意各种dp[ ][0][0][0]都是1。自己体现在那个dp[ ][ ][ ][0]的转移中了。
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int N=1005,M=205; const ll mod=1e9+7; int n,m,lm; ll dp[2][M][M][2]; char a[N],b[M]; int rdn() { int ret=0,fx=1;char ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)fx=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)(ret*=10)+=ch-‘0‘,ch=getchar(); return ret*fx; } int main() { n=rdn();m=rdn();lm=rdn(); scanf("%s",a+1);scanf("%s",b+1); dp[0][0][0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=lm;k++) { dp[i&1][j][k][0]=dp[i&1][j][k][1]=0; dp[i&1][j][k][0]=(dp[(i-1)&1][j][k][0]+dp[(i-1)&1][j][k][1])%mod; if(a[i]==b[j]&&k) dp[i&1][j][k][1]=(dp[(i-1)&1][j-1][k-1][0]+dp[(i-1)&1][j-1][k][1]+dp[(i-1)&1][j-1][k-1][1])%mod;//!第3项 } printf("%lld",(dp[n&1][m][lm][0]+dp[n&1][m][lm][1])%mod); return 0; }
原文：https://www.cnblogs.com/Narh/p/9196244.html