Description
有两个仅包含小写英文字母的字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一 个新的字符串,请问有多少种方案可以使得这个新串与字符串 B 相等?注意:子串取出 的位置不同也认为是不同的方案。
Input
第一行是三个正整数 n,m,k,分别表示字符串 A 的长度,字符串 B 的长度,以及问题描述中所提到的 k,每两个整数之间用一个空格隔开。
第二行包含一个长度为 n 的字符串,表示字符串 A。 第三行包含一个长度为 m 的字符串,表示字符串 B。
Output
输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求输出答案对 1,000,000,007 取模的结果。
Sample Input
样例输入1：
6 3 1
aabaab
aab
样例输入2：
6 3 2
aabaab
aab
Sample Output
样例输出1：
2
样例输出2：
7
Hint
样例解释：
所有合法方案如下：（加下划线的部分表示取出的子串）
样例一：aab aab / aab aab
样例二：a ab aab / a aba ab / a a ba ab / aab a ab / aa b aab / aa baa b / aab aa b
样例三：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。
Source
NOIP2015，动态规划
这个题很容易想到三维的dp状态，dp[i][j][k]，表示A串到i位置，B串到j位置，已经用了k个串的方案数。。。
就是很常规的字符串dp状态。。。然后转移也是字符串dp的常规套路，按a[i]==b[j]和a[i]!=a[j]分别转移一下。。。
大致是这样：
当a[i]!=b[j]时，
dp[i][j][k]+=dp[i-1][j][k](跳过A串的i位置)
a[i]==b[j]时，
dp[i][j][k]+=dp[i-1][j-1][k-1](新开一个串);
dp[i][j][k]+=dp[i-1][j][k](跳过A串的i位置);
dp[i][j][k]+=dp[i-1][j-1][k](表示从上一个串接过来)
但是第三个转移有点问题，因为要从上一个串接过来的话，需要a[i-1]==b[j-1]才能转移。
那么我们多开一维，dp[i][j][k][0/1]第四维表示i和j是否匹配上了(把第一维滚掉)。。。
然后转移就很simple了。。。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define RG register
using namespace std;
typedef long long ll;
const int N=100050;
const int Mod=1e9+7;
int n,m,k;
int dp[2][205][205][2];
char a[N],b[N];
int main(){
freopen("2015substring.in","r",stdin);
freopen("2015substring.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
scanf("%s",a+1);scanf("%s",b+1);
int cur=0;
for(RG int i=1;i<=n;i++){
dp[cur][0][0][1]=1;cur^=1;
memset(dp[cur],0,sizeof(dp[cur]));
for(RG int j=1;j<=i&&j<=m;j++){
for(RG int p=1;p<=k;p++){
if(a[i]==b[j]){
(dp[cur][j][p][1]+=dp[cur^1][j-1][p][1])%=Mod;
(dp[cur][j][p][1]+=(dp[cur^1][j-1][p-1][1]+dp[cur^1][j-1][p-1][0])%Mod)%=Mod;
(dp[cur][j][p][0]+=(dp[cur^1][j][p][0]+dp[cur^1][j][p][1])%Mod)%=Mod;
}
else{
(dp[cur][j][p][0]+=(dp[cur^1][j][p][0]+dp[cur^1][j][p][1])%Mod)%=Mod;
}
}
}
}
printf("%d
",(dp[cur][m][k][0]+dp[cur][m][k][1])%Mod);
return 0;
}