首页 > 代码库 > [NOIP2015] 子串substring 题解

[NOIP2015] 子串substring 题解

【题目描述】

有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串,然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串B相等?注意:子串取出的位置不同也认为是不同的方案。

由于答案可能很大,所以这里要求输出答案对1,000,000,007取模的结果。

【样例输入1】

6 3 1

aabaab

aab

【样例输出1】

2

【样例输入2】

6 3 2

aabaab

aab

【样例输出2】

7

【样例输入3】

6 3 3

aabaab

aab

【样例输出3】

7

技术分享

【数据规模与约定】

对于100%的数据:1≤n≤1000,1≤m≤200,1≤k≤m。

【解法】

还好吧……一个DP……不过细节比较多,难度不小。

我们令f[i][j][k][0/1]表示A串用了前i个字符,B串已覆盖前j个字符,目前为止已经选了k个子串,最后的0/1表示A串的这个字符选了没有(0没选,1选了)。

为了得出状态转移方程,我们分情况讨论:

先看f[i][j][k][1](当前位选了),显然当且仅当a[i]=b[j]的时候它才有意义,否则f[i][j][k][1]=0。

到这个状态有三种方法:

1. 上一位没有选,新开一个子串

2. 上一位选了,延续这个子串

3. 上一位选了,但是仍然新开一个子串

因此,我们有

f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1]。

状态转移方程中的三项分别对应上述三种情况。注意,因为我们规定了A的这一位必须选(因为状态的最后一维是1),所以所有前驱状态一定是f[i-1][j-1][…][…]。

然后讨论另一种情况:这个字符不选。

这个比较简单,到这个状态有两种方法:

1. 上一位没有选,现在仍然不选

2. 上一位选了,结束这个子串

因此,我们有

f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]。

合起来就是

f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1](a[i]=b[j])

f[i][j][k][1]=0(a[i]!=b[j])

f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]

状态转移方程有了,边界也容易确定:f[0][0][0][0]=1。至于最终答案,显然是f[n][m][k][0]+f[n][m][k][1]。

这里有O(nmk)个状态,转移是O(1)的,因此总复杂度O(nmk),完全够用(毕竟常数不大)。

然后,注意一些可能越界的问题(j/k=0的时候不要j/k-1),再用滚动数组压掉第一维,就可以AC了。

贴个代码:

技术分享
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=1010,maxm=210;int n,m,c,i=1,f[2][maxm][maxm][2];char a[maxn],b[maxm];int main(){#define MINE#ifdef MINE    freopen("2015substring.in","r",stdin);    freopen("2015substring.out","w",stdout);#endif    scanf("%d%d%d %s %s",&n,&m,&c,a+1,b+1);    f[0][0][0][0]=1;    for(int d=1;d<=n;d++,i=!i)for(int j=0;j<=d&&j<=m;j++)for(int k=0;k<=j&&k<=d&k<=c;k++){        f[i][j][k][0]=0;        if(d-1>=j){            (f[i][j][k][0]+=f[!i][j][k][0])%=1000000007;            (f[i][j][k][0]+=f[!i][j][k][1])%=1000000007;        }        f[i][j][k][1]=0;        if(j&&a[d]==b[j]){            if(k){                (f[i][j][k][1]+=f[!i][j-1][k-1][0])%=1000000007;                (f[i][j][k][1]+=f[!i][j-1][k-1][1])%=1000000007;            }            (f[i][j][k][1]+=f[!i][j-1][k][1])%=1000000007;        }    }    printf("%d\n",(f[!i][m][c][0]+f[!i][m][c][1])%1000000007);#ifndef MINE    printf("\n--------------------DONE--------------------\n");    for(;;);#endif    return 0;}
View Code

【后记】

去年联赛的Day2 T2……难度还可以,主要是状态表示和转移方程比较麻烦,也不太好想,有些细节问题略恶心。

很久没刷过DP了……自己DP本来就弱,不过好歹自己想出来了解法,也算是个安慰吧(我才不会说其实我已经从各种渠道知道了这题的复杂度是O(nmk)的)。

为了这题废了一节课……努力吧……

[NOIP2015] 子串substring 题解