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

作者: wjyyy 分类: DP,解题报告 发布时间: 2018-10-18 10:33

点击量:31

 

    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 ba ab a a ba aba a b

      aab / 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;
}

说点什么

avatar
  Subscribe  
提醒
/* */