描述
有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串&＃xff0c;然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一 个新的字符串&＃xff0c;请问有多少种方案可以使得这个新串与字符串B相等&＃xff1f;注意&＃xff1a;子串取出 的位置不同也认为是不同的方案。
【数据规模与约定】 对于第1组数据&＃xff1a;1<&＃61;n<&＃61;500&＃xff0c;1<&＃61;m<&＃61;50&＃xff0c;k&＃61;1; 对于第2组至第3组数据&＃xff1a;1<&＃61;n<&＃61;500&＃xff0c;1<&＃61;m<&＃61;50&＃xff0c;k&＃61;2; 对于第4组至第5组数据&＃xff1a;1<&＃61;n<&＃61;500&＃xff0c;1<&＃61;m<&＃61;50&＃xff0c;k&＃61;m; 对于第1组至第7组数据&＃xff1a;1<&＃61;n<&＃61;500&＃xff0c;1<&＃61;m<&＃61;50&＃xff0c;1<&＃61;k<&＃61;m; 对于第1组至第9组数据&＃xff1a;1<&＃61;n<&＃61;1000&＃xff0c;1<&＃61;m<&＃61;100&＃xff0c;1<&＃61;k<&＃61;m; 对于所有10组数据&＃xff1a;1<&＃61;n<&＃61;1000&＃xff0c;1<&＃61;m<&＃61;200&＃xff0c;1<&＃61;k<&＃61;m。
输入
输入文件名为substring.in。 第一行是三个正整数n&＃xff0c;m&＃xff0c;k&＃xff0c;分别表示字符串A的长度&＃xff0c;字符串B的长度&＃xff0c;以及问 题描述中所提到的k&＃xff0c;每两个整数之间用一个空格隔开。 第二行包含一个长度为n的字符串&＃xff0c;表示字符串A。 第三行包含一个长度为m的字符串&＃xff0c;表示字符串B。
输出
输出文件名为substring.out。 输出共一行&＃xff0c;包含一个整数&＃xff0c;表示所求方案数。由于答案可能很大&＃xff0c;所以这里要求输 出答案对1,000,000,007取模的结果。
样例输入[复制]
6 3 1
aabaab
aab
样例2&＃xff1a;
6 3 2
aabaab
aab
样例3&＃xff1a;
6 3 3
aabaab
aab
样例输出[复制]
2
样例2&＃xff1a;
7
样例3&＃xff1a;
7
f[i][j][k]&＃61;f[i-1][j-1][k-1]&＃43;f[i-1][j-1][k]
s[i][j][k]&＃61;f[i-1][j-1][k-1]&＃43;s[i-1][j-1][k]
显然如果a[i]!&＃61;b[j]的话直接s[i][j][k]就是0
接下来我们考虑f[i][j][k]的转移&＃xff0c;前提还是一样的
由于我现在的决策已经变成了选或者不选的问题了&＃xff0c;已经与匹不匹配无关了
如果我选择这个进行匹配的话&＃xff0c;如果是使用当前的字符&＃xff0c;我们就要加上一定使用这个字符的方案数s[i][j][k]&＃xff0c;如果你说我选上并不匹配怎么办&＃xff1f;注意如果本身不匹配那么s[i][j][k]是0&＃xff0c;选上没有意义
如果我们选择不用的话&＃xff0c;自然就直接由上一个状态转移过来f[i-1][j][k]
方程就是
f[i][j][k]&＃61;s[i][j][k]&＃43;f[i-1][j][k]
为什么我们这个没有判断说是a[i]&＃61;&＃61;b[j]?因为与匹配无关&＃xff0c;我们关心的是选上去的方案数的贡献和不选的贡献&＃xff0c;为什么我们不在s里面解决&＃xff1f;因为选与不选是一个状态&＃xff0c;自成一家或者与前面混合又是一个状态&＃xff0c;两个状态不能混在一起&＃xff01;&＃xff01;
最后发现数组不够用啊&＃xff0c;我们尝试滚掉一维
为什么我们能滚掉一维&＃xff1f;因为在写循环的时候我们是按i作为第一维&＃xff0c;而第一维i使用完之后只会对i&＃43;1做出贡献&＃xff0c;就是背包问题&＃xff0c;于是我们就复用数组
至于滚掉一维数组后后面的循环顺序就应该倒过来&＃xff0c;因为你要用之前的状态&＃xff0c;如果你正向就会用到刚算好的状态造成重复&＃xff08;这也是多重背包的原理&＃xff09;&＃xff0c;就可以覆盖前面
还是照例总结一下
这道题其实告诉我如果有多个不同的状态&＃xff08;红字&＃xff09;就应该尝试分开他们来进行讨论&＃xff0c;不要固执于使用一个数组&＃xff0c;这些状态是交融但是不完全等同的&＃xff0c;应该及时分开处理
记得取模
代码在下面了&＃xff1a;
1 #include
2 #include
3 using namespace std;
4 char a[100000],b[10000];
5 int f[1000][1000];
6 int s[1000][1000];const int mod&＃61;1000000007;
7 int main() {
8 int n,m,k;
9 cin>>n>>m>>k;
10 for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)cin>>a[i];
11 for(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;)cin>>b[i];
12 f[0][0]&＃61;1;
13 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
14 for(int j&＃61;m;j>&＃61;1;j--){
15 for(int l&＃61;k;l>&＃61;1;l--){
16 if(a[i]&＃61;&＃61;b[j])s[j][l]&＃61;f[j-1][l-1]&＃43;s[j-1][l];
17 else s[j][l]&＃61;0;
18 s[j][l]%&＃61;mod;
19 f[j][l]&＃61;f[j][l]&＃43;s[j][l];
20 f[j][l]%&＃61;mod;
21 //cout<
22 }
23 }
24 }
25 cout<<f[m][k];
26 return 0;
27 }
一道好题啊
京公网安备 11010802041100号