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 aabSample Output
样例输出1：
2样例输出2：
7Hint
样例解释：
所有合法方案如下：（加下划线的部分表示取出的子串） 样例一：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#include #include #include #include #define RG registerusing 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\n",(dp[cur][m][k][0]+dp[cur][m][k][1])%Mod); return 0;}