网站系统性能定义,安卓优化大师下载,医院网站前置审批,优化网络速度 4560 NOIP2015 D2T2 子串时间限制: 1 s空间限制: 128000 KB题目等级:黄金 Gold
题目描述 Description
有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串#xff0c;然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新… 4560 NOIP2015 D2T2 子串时间限制: 1 s空间限制: 128000 KB题目等级:黄金 Gold
题目描述 Description
有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串请问有多少种方案可以使得这个新串与字符串B相等注意子串取出的位置不同也认为是不同的方案。
输入描述 Input Description
第一行是三个正整数nmk分别表示字符串A的长度字符串B的长度以及问题描述中所提到的k每两个整数之间用一个空格隔开。
第二行包含一个长度为n的字符串表示字符串A。 第三行包含一个长度为m的字符串表示字符串B。
输出描述 Output Description
输出共一行包含一个整数表示所求方案数。由于答案可能很大所以这里要求输出答案对1,000,000,007取模的结果。
样例输入 Sample Input
【Input1】
6 3 1
aabaab
aab
【Input2】
6 3 2
aabaab
aab
【Input3】
6 3 3
aabaab
aab
样例输出 Sample Output
【Output1】
2
【Output2】
7
【Output3】
7
数据范围及提示 Data Size Hint
对于第1组数据1≤n≤5001≤m≤50k1
对于第2组至第3组数据1≤n≤5001≤m≤50k2
对于第4组至第5组数据1≤n≤5001≤m≤50km
对于第1组至第7组数据1≤n≤5001≤m≤501≤k≤m
对于第1组至第9组数据1≤n≤10001≤m≤1001≤k≤m
对于所有10组数据1≤n≤10001≤m≤2001≤k≤m。 /*
方案数DP滚动数组优化.
f[i][j][p][]表示A串前i个字符B串前j个字符组成k个贡献的方案数.
最后一维对当前字符用不用讨论.
当前考虑两种状态:两个字符相等.两个字符不等.
关于取模的问题相关(abc)%p((ab)%pc)%p.
*/
#includeiostream
#includecstdio
#define mod 1000000007
#define MAXN 1001
#define MAXM 201
using namespace std;
int f[2][MAXM][MAXM][2],n,m,k;
char s1[MAXN],s2[MAXM];
int read()
{int x0,f1;char chgetchar();while(ch0||ch9) {if(ch-)f-1;chgetchar();}while(ch0ch9)xx*10ch-48,chgetchar();return x*f;
}
int main()
{nread();mread();kread();for(int i1;in;i) cins1[i];for(int i1;im;i) cins2[i];f[0][0][0][0]f[1][0][0][0]1;for(int i1;in;i)for(int j1;jmin(i,m);j)for(int p1;pk;p){int nowi1,last(i-1)1;if(s1[i]s2[j]) f[now][j][p][1]((f[last][j-1][p][1]f[last][j-1][p-1][0])%modf[last][j-1][p-1][1])%mod,f[now][j][p][0](f[last][j][p][0]f[last][j][p][1])%mod;else f[now][j][p][1]0,f[now][j][p][0](f[last][j][p][0]f[last][j][p][1])%mod;; }printf(%d,(f[n1][m][k][0]%modf[n1][m][k][1]%mod)%mod);return 0;
} 转载于:https://www.cnblogs.com/nancheng58/p/6070802.html
