洛谷 P2679 NOIp2015提高组 子串 题解【DP】【字符串】

点击量：194

    NOIp前复习想到这个之前做过的毒瘤DP，没想到现在依然毒瘤。

目录

题目描述

有两个仅包含小写英文字母的字符串\(A\)和\(B\)。

 

现在要从字符串\(A\)中取出\(k\)个互不重叠的非空子串，然后把这\(k\)个子串按照其在字符串\(A\)中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串\(B\)相等？

 

注意：子串取出的位置不同也认为是不同的方案。

 

输入输出格式

输入格式：

第一行是三个正整数\(n,m,k\)，分别表示字符串\(A\)的长度，字符串\(B\)的长度，以及问题描述中所提到的\(k\)，每两个整数之间用一个空格隔开。

 

第二行包含一个长度为\(n\)的字符串，表示字符串\(A\)。

 

第三行包含一个长度为\(m\)的字符串，表示字符串\(B\)。

 

输出格式：

一个整数，表示所求方案数。

 

由于答案可能很大，所以这里要求输出答案对\(1000000007\)取模的结果。

 

输入输出样例

输入样例#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：aab aab / aab aab

样例2：a ab aab / a aba ab / a a ba ab / aab a ab

      aab aab / aa baa b / aab aa b 

样例3：a a b aab / a a baa b / a ab a a b / a aba a b

      a a b a a b / a a ba a b / aab a a b

对于第\(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是从前面某一个位置转移，那么选的这个位置到当前位置的串就作为第\(i\)个子串。而这样不用前缀和优化是\(n^2m^2\)的，基本拿不到分，因此要换一种DP思路。

    我们知道，同一个串中的元素一定是相邻的，那么如果\(s\)中的前一个元素可以作为第\(x\)个串，则\(s\)中的这个元素如果匹配成功也可以作为第\(x\)个串，或者另起炉灶，作为第\(x+1\)个串。可见接着作为第\(x\)个串的条件更苛刻，甚至重新开始作为第\(x+1\)个串可以连接到前面任意一个合法的\(x\)个串的位置。

    考虑可以相邻转移，定义\(f_{(i,j,k)}\)表示\(A\)串第\(i\)位作为\(B\)串第\(k\)段第\(j\)位，这一位置如果有值必须要求\(A_i\)匹配上了\(B_j\)，如果\(A_{i-1}\)匹配上了\(B_{j-1}\)，它可以从\(f_{(i-1,j-1,k)}\)转移；但无论如何都是可以从前面的\(k-1\)转移的，则有

$$f_{(i,j,k)}=\left\{\begin{matrix}
& \sum_{t=1}^{t<i}f_{(t,j-1,k-1)} & A_{i-1}\not=B_{j-1}\\
& f_{(i-1,j-1,k)}+\sum_{t=1}^{t<i}f_{(t,j-1,k-1)} & A_{i-1}=B_{j-1}
\end{matrix}\right.A_i=B_j$$

    因此这样的转移方程时间复杂度为\(O(nm^3)\)（\(k\)与\(m\)同阶），可以拿到70分。

    然后只要拿前缀和优化一下那个\(\sum\)就可以过掉了。

    总结：这个题其实不难，但是由于一开始钻到错误的DP方式中，导致了方向上的偏离。以后做DP不能按习惯的思路去做，要考虑它是不是不同的方式。事情的关键主要是优化复杂度。

Code：

#include<cstdio>
#include<cstring>
int Min(int x,int y)
{
    return x<y?x:y;
}
char s[1010],t[1010];
int f[2][205][205],g[205][205];
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s",s+1);
    scanf("%s",t+1);
    g[0][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=Min(m,i);j;--j)
            for(int p=Min(j,k);p;--p)
                if(s[i]==t[j])
                {
                    f[i&1][j][p]=g[j-1][p-1];
                    if(s[i-1]==t[j-1])
                        f[i&1][j][p]=(f[i&1][j][p]+f[i&1^1][j-1][p])%1000000007;
                    g[j][p]=(g[j][p]+f[i&1][j][p])%1000000007;
                }
    printf("%d\n",g[m][k]);
    return 0;
}