我开始想到了这个四维数组f[ i ][ j ][ k ][ 0/1 ]表示到A数组i这个位置和B匹配到了j这个位置 用了几个子串 当前是否用
然后我就搞搞搞搞搞搞 又换成了f[ i ][ j ][ k ][ 0/1 ]表示到A数组i这个位置和B匹配到了j这个位置 当前子串多长 当前是否用
然后就没时间了QAQ 我是个弟弟
状态转移也没考虑好 没有考虑到不能选时是0
然后我就可以发现 当前i的状态只与前一个状态有关 故我们就可以愉快地把第一个滚掉
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define rg register 4 const int N=1000+5,M=200+5,inf=1e9+7; 5 int n,m,K,dp[2][M][M][2]; 6 //到a串的第i个位置使用p个子串匹配b串前j位字符 第i个位置选或不选 7 char a[N],b[N]; 8 inline int rd() 9 { 10 int x=0,w=0;char ch=0; 11 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 12 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 13 return w?-x:x; 14 } 15 16 int main() 17 { 18 n=rd(),m=rd(),K=rd(); 19 scanf("%s%s",a+1,b+1); 20 dp[0][0][0][0]=dp[1][0][0][0]=1; 21 bool now=1; 22 for(int i=1;i<=n;i++,now^=1) 23 for(int j=1;j<=m;j++) 24 for(int k=1;k<=K;k++) 25 { 26 if(a[i]==b[j]) 27 { 28 dp[now][j][k][0]=(dp[now^1][j][k][0]+dp[now^1][j][k][1])%inf;//选 29 dp[now][j][k][1]=(dp[now^1][j-1][k][1]+(dp[now^1][j-1][k-1][0]+dp[now^1][j-1][k-1][1])%inf)%inf; //不选 30 } 31 else 32 { 33 dp[now][j][k][0]=(dp[now^1][j][k][0]+dp[now^1][j][k][1]);//不选 34 dp[now][j][k][1]=0;//选不了 35 } 36 } 37 printf("%d",(dp[n&1][m][K][0]+dp[n&1][m][K][1])%inf); 38 return 0; 39 }