Luogu 2679 NOIP 2015 子串 （动态规划）

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

6 3 1 aabaab aab

Sample Output

2

Http

Luogu:https://www.luogu.org/problem/show?pid=2679

Source

动态规划

解决思路

设\(F[i][j][k][0/1]\)表示当前选到\(A\)的第\(i\)位，匹配到\(B\)的第\(j\)位，是第\(k\)个子串。0表示\(A\)的该位必选，1表示选or不选都行。 考虑两种情况 若\(A[i]==B[j]\)，则可以将新的这个字符串接在前一个子串后面，这时要求前面一个必选，则\(F[i][j][k][0]\)可以从\(F[i-1][j-1][k][0]\)转移过来，也可以新开一个子串，此时对前面的字符是否选取没有要求，所以可以从\(F[i-1][j-1][k-1][1]\)转移来。 若\(A[i]!=B[j]\)则\(F[i][j][k][0]=0\)。 在求完\(F[i][j][k][0]\)后，\(F[i][j][k][1]=F[i][j][k][0]+F[i-1][j][k][1]\)。注意滚动数组。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int maxN=1010; const int maxM=210; const int Mod=1000000007; const int inf=2147483647; int n,m,K; char A[maxN]; char B[maxM]; int F[2][maxM][maxM][2]; int main() { scanf("%d%d%d",&n,&m,&K); scanf("%s",(A+1)); scanf("%s",(B+1)); memset(F,0,sizeof(F)); F[0][0][0][1]=F[1][0][0][1]=1;//初始值 for (int i=1;i<=n;i++) { F[i%2][0][0][1]=1; for (int j=1;j<=m;j++) for (int k=1;k<=K;k++) { if (A[i]==B[j]) F[i%2][j][k][0]=(F[(i-1)%2][j-1][k][0]+F[(i-1)%2][j-1][k-1][1])%Mod; else F[i%2][j][k][0]=0; F[i%2][j][k][1]=(F[i%2][j][k][0]+F[(i-1)%2][j][k][1])%Mod; } } printf("%d\n",F[n%2][m][K][1]%Mod); return 0; }

转载于:https://www.cnblogs.com/SYCstudio/p/7628986.html

相关资源：JAVA上百实例源码以及开源项目