luogu P2679——子串

题目描述有两个仅包含小写英文字母的字符串 AAA 和 BBB 。现在要从字符串 AAA 中取出 kkk 个互不重叠的非空子串，然后把这 kkk 个子串按照其在字符串 AAA 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 BBB 相等？注意：子串取出的位置不同也认为是不同的方案。 输入输出格式 输入格式：第一行是三个正整数 n,m,kn,m,kn,m,k ，分别表示字符串 AAA 的长度，字符串 BBB 的长度，以及问题描述中所提到的 kkk ，每两个整数之间用一个空格隔开。第二行包含一个长度为 nnn 的字符串，表示字符串 AAA 。第三行包含一个长度为 mmm 的字符串，表示字符串 BBB 。输出格式：输出共一行，包含一个整数，表示所求方案数。由于答案可能很大，所以这里要求输出答案对 100000000710000000071000000007 取模的结果。输入输出样例 输入样例#1： 复制6 3 1 aabaab aab输出样例#1： 复制2输入样例#2： 复制6 3 2 aabaab aab输出样例#2： 复制7输入样例#3： 复制6 3 3 aabaab aab输出样例#3： 复制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。 题面

 如题，我们分析一下。好像是一个dp？？？

对啊好像是。

那么想一下状态；

dp[ i ][ j ][ k ]表示a串匹配到i的位置，b串匹配到j的位置，用了k个子串的方案数；

当a[i]==b[j]时，则有两种情况：

一是可以自己成为一个子串：dp[i-1][j-1][k-1];

二是和前一个凑成一个子串：dp[i-1][j-1][k];

那么转移方程就为

dp[ i ][ j ][ k ]=（dp[i-1][j-1][k-1]+dp[i-1][j-1][k]）%mod；

可是好像有一些问题，就是这一个位置就算他们相等也可以不选，跳过；

那么我们就要重设状态了；

dp[ i ][ j ][ k ][0/1]表示当前这个字符选（0）/选不选无所谓( 1 )的方案数；

但是我们看一下数据范围1000*200*200*2*4（int的字节）/1024/1024=305.17578125>128；

肯定是开不下的，那我们尝试把第一维抹掉；

dp[ j ][ k ][0]表示b字符串中匹配到j这个位置，用了k个子串，并且当前这个位置一定选的方案数；

dp[ j ][ k ][1]表示b字符串中匹配到j这个位置，用了k个子串，并且当前这个位置不一定选的方案数；

当a[i]==b[j]时，dp[ j ][ k ][0]仍旧有两种转移

一是可以自己成为一个子串,不管前面一个选或不选：dp[j-1][k-1][1];

二是和前一个凑成一个子串：dp[j-1][k][0];

那么dp[ j ][ k ][1]的转移为

一当前这一位取：dp[ j ][ k ][0]；

二当前这一位不取：dp[ j ][ k ][1]；

如果a[ i ]!=a[ j ]

那么当前b里这一位选的方案数肯定是0：dp[j][k][0]=0；

最后只需要输出dp[b字符串的长度][子串总数][1]即可，因为最后一位可取可不取；

既然是dp方程，肯定要有初值的啊

dp[0][0][0]=dp[0][0][1]=1;(某神犇传授的经验，一般求方案数的dp，边界条件都是1）

然后就结束了；

感谢叶犇犇的指导；

贴一发 ↑ 神犇的博客

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int mod=1000000007; char a[1200],b[210]; int n,m,tot; int dp[210][210][3]; int main() {scanf("%d%d%d",&n,&m,&tot);cin>>a+1;cin>>b+1;/*for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;for(int i=1;i<=m;i++)cout<<b[i]<<" ";*/dp[0][0][0]=dp[0][0][1]=1;//第三维是零表示这一位必选，是1表示选不选都行； for(int i=1;i<=n;i++)for(int j=m;j>=1;j--)for(int k=1;k<=tot;k++){if(a[i]==b[j]){dp[j][k][0]=(dp[j-1][k][0]+dp[j-1][k-1][1])%mod;//独自成一串（dp[j-1][k-1][1]）或者是与前面成一串 （ dp[j-1][k][0]）； dp[j][k][1]=(dp[j][k][0]+dp[j][k][1])%mod;//当前这一位取的话就是dp[j][k][0]，不取的话就是dp[j][k][1]（这其实是从上一位转移过来的）； }elsedp[j][k][0]=0; }printf("%d",dp[m][tot][1]);return 0; } 标程

转载注明来源，谢谢；

转载于:https://www.cnblogs.com/royal-8/p/9084860.html

总结

以上是生活随笔为你收集整理的luogu P2679——子串的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。