题目背景
无
题目描述
有两个仅包含小写英文字母的字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一 个新的字符串,请问有多少种方案可以使得这个新串与字符串 B 相等?注意:子串取出 的位置不同也认为是不同的方案。
输入输出格式
输入格式:
输入文件名为 substring.in。
第一行是三个正整数 n,m,k,分别表示字符串 A 的长度,字符串 B 的长度,以及问
题描述中所提到的 k,每两个整数之间用一个空格隔开。 第二行包含一个长度为 n 的字符串,表示字符串 A。 第三行包含一个长度为 m 的字符串,表示字符串 B。
输出格式:
输出文件名为 substring.out。 输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求[b]输出答案对 1,000,000,007 取模的结果。[/b]
输入输出样例
输入样例#1:
1 2 3 |
6 3 1 aabaab aab |
输出样例#1:
1 |
2 |
输入样例#2:
1 2 3 |
6 3 2 aabaab aab |
输出样例#2:
1 |
7 |
输入样例#3:
1 2 3 |
6 3 3 aabaab aab |
输出样例#3:
1 |
7 |
说明
对于第 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。
Solution
终于自己推出了一道DP,开心!这道DP不算难,我写的f[i][j][k][p]表示字符串A中前i个与字符串B中前j个,在A中取出了k段,A[i]是否在这k段中(在为1不在为0),然后将第三维滚动即可!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<iostream> #include<cstdio> using namespace std; const int mo=1000000007; int n,m,K,f[1005][205][2],g[1005][205][2]; char s1[1005],s2[205]; int main() { scanf("%d%d%d",&n,&m,&K); scanf("%s",s1+1); scanf("%s",s2+1); for (int i=0;i<=n;i++) g[i][0][0]=1; for (int k=1;k<=K;k++) { for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { f[i][j][0]=f[i][j][1]=0; f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mo; if (s1[i]==s2[j]) f[i][j][1]=((g[i-1][j-1][0]+f[i-1][j-1][1])%mo+g[i-1][j-1][1])%mo; } for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) g[i][j][0]=f[i][j][0],g[i][j][1]=f[i][j][1]; } printf("%d\n",(f[n][m][0]+f[n][m][1])%mo); return 0; } |