题目描述

有两个仅包含小写英文字母的字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串，然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串，请问有多少种方案可以使得这个新串与字符串 B 相等？注意：子串取出的位置不同也认为是不同的方案。

输入描述:

第一行是三个正整数 n，m，k，分别表示字符串 A 的长度，字符串 B 的长度，以及问题描述中所提到的 k，每两个整数之间用一个空格隔开。
第二行包含一个长度为 n 的字符串，表示字符串 A。
第三行包含一个长度为 m 的字符串，表示字符串 B。

输出描述:

输出共一行，包含一个整数，表示所求方案数。由于答案可能很大，所以这里要求输出答案对 1,000,000,007 取模的结果。

示例1

输入
6 3 1
aabaab
aab
输出
2
说明
样例 1所有合法方案如下：（加下划线的部分表示取出的子串）
aab aab / aab aab

示例2

输入
6 3 2
aabaab
aab
输出
7
说明
样例 2：所有合法方案如下：（加下划线的部分表示取出的子串）
a ab aab / a aba ab / a a ba ab / aab a ab
aa b aab/ aa baa b / aab aa b

示例3

输入
6 3 3
aabaab
aab
输出
7
说明
样例 3所有合法方案如下：（加下划线的部分表示取出的子串）
a a b aab / a a baa b / a ab a a b / a aba a b
a a b a a b /a a ba a b / aab a a b

备注

对于第 1 组数据：1≤n≤500，1≤m≤50，k=1；
对于第 2 组至第 3 组数据：1≤n≤500，1≤m≤50，k=2；
对于第 4 组至第 5 组数据：1≤n≤500，1≤m≤50，k=m；
对于第 1 组至第 7 组数据：1≤n≤500，1≤m≤50，1≤k≤m；
对于第 1 组至第 9 组数据：1≤n≤1000，1≤m≤100，1≤k≤m；
对于所有 10 组数据：1≤n≤1000，1≤m≤200，1≤k≤m。

解答

定义状态表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符用了 k 个子串，第四维为 1 表示 A 字符串的第 i 个字符必须被选出，为 0 表示 A 字符串的第 i 个字符不能被选出。
那么很容易得出转移：
1、对于任意一个 。
2、
3、
最后结果即为。
考虑到空间问题，这里滚动 f的第一维以节省空间。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read(){
    int f=1,x=0;
    char c=getchar();
    while (c<'0'||c>'9'){if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f*x;
}
const int tt=1e9+7;
const int maxn=1e3+5;
int k,n,m,g,h,o,p,r;
char a[maxn],b[maxn];
long long f[2][maxn][maxn][2];
int main(){
    n=read();
    m=read();
    r=read();
    scanf("%s",a+1);
    scanf("%s",b+1);
    f[0][0][0][0]=1;
    for (int i=1;i<=n;i++){
        p=i&1;
        f[p][0][0][0]=1;
        for  (int j=1;j<=min(i,m);j++)
        for (int k=1;k<=min(j,r);k++){
            f[p][j][k][0]=f[p][j][k][1]=0;
            f[p][j][k][0]=(f[p^1][j][k][0]+f[p^1][j][k][1])%tt;
            if (a[i]==b[j]){
                f[p][j][k][1]=(f[p^1][j-1][k][1]+f[p^1][j-1][k-1][0]%tt);
                (f[p][j][k][1]+=f[p^1][j-1][k-1][1])%=tt;
            }
        }
    }
    printf("%d\n",(f[n&1][m][r][0]+f[n&1][m][r][1])%tt);
    return 0;
}


来源：Fatalzyc