【题意】求从字符串A中取出k个互不重叠的非空子串顺序拼接形成B的方案数。n<=1000,m<=100,k<=m。

【算法】动态规划

【题解】这题主要是将从i-l转移变成从i-1转移，从而省略l这一维的枚举（等价于记录前缀和，将信息顺序传递过来）。

f[i][j][k]表示字符串A到i，字符串B到j，已用k个子串的方案数，特别地，g[i][j][k]表示选择A[i]的前提下字符串A到i，字符串B到j，已用k个子串的方案数。

g[i][j][k]=f[i-1][j-1][k-1]+g[i-1][j-1][k]，A[i]=B[j]　　新开一个子串（k-1）或不新开（k）

f[i][j][k]=g[i][j][k]+f[i-1][j][k]　　选择或不选择

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=1010,maxm=210,MOD=1e9+7;int f[2][maxm][maxm],g[2][maxm][maxm],n,m,kind;char A[maxn],B[maxm];int MO(int x){
    return x>=MOD?x-MOD:x;}int main(){    scanf("%d%d%d",&n,&m,&kind);    scanf("%s%s",A+1,B+1);    int x=0;    f[0][0][0]=f[1][0][0]=1;    for(int i=1;i<=n;i++){        x=1-x;        for(int j=1;j<=m;j++){            for(int k=1;k<=kind;k++){                if(k>j){f[x][j][k]=g[x][j][k]=0;continue;}                if(A[i]==B[j])g[x][j][k]=MO(f[1-x][j-1][k-1]+g[1-x][j-1][k]);else g[x][j][k]=0;                f[x][j][k]=MO(g[x][j][k]+f[1-x][j][k]);            }        }    }    printf("%d",f[x][m][kind]);    return 0;}