洛谷 P2679 子串 解题报告

时间：2022-10-09 17:29:14

P2679 子串

题目描述

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

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

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

输入输出格式

输入格式：

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

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

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

输出格式：

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

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

说明：

对于所有 10 组数据: \(1≤n≤1000,1≤m≤200,1≤k≤m\)。

这题好难想orz,,,

令dp[l][i][j][0/1]代表匹配到第\(l\)段时，A串匹配到第\(i\)段，B串匹配到第\(j\)段，A串的第\(i\)位是否处于匹配。

关于第四维的设计，我们由 B串必须完整匹配，而A串不需要完整匹配 推出

转移：

\(dp[l][i][j][1]=dp[l-1][i-1][j-1][1]+dp[l-1][i-1][j-1][0]+dp[l][i-1][j-1][1],a[i]==b[j]\)

\(dp[l][i][j][0]=dp[l][i-1][j][0]+dp[l][i-1][j][1]\)

这样空间肯定炸了的，我们考虑用滚动数组优化。

但是滚动数组优化的话，我们得稍稍处理一下\(a[i]!=b[j]\)时\(dp[l][i][j][1]\)的值为0，还有起始边界的置0，否则循环用会出问题。

一个细节，加三项时每两项都得膜，否则只有40分好像。。

code:

#include <cstdio>

const int N=1010;

const int M=203;

const int mod=1000000007;

char c1[N],c2[M];

int n,m,k,dp[2][N][M][2];

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    scanf("%s%s",c1+1,c2+1);

    for(int i=0;i<=n;i++)

        dp[0][i][0][0]=1;

    for(int l=1;l<=k;l++)

    {

        for(int i=1;i<=n;i++)

            for(int j=1;j<=i;j++)

            {

                if(c1[i]==c2[j])

                    dp[l&1][i][j][1]=((dp[(l-1)&1][i-1][j-1][1]+dp[(l-1)&1][i-1][j-1][0])%mod+dp[l&1][i-1][j-1][1])%mod;

                else

                    dp[l&1][i][j][1]=0;

                dp[l&1][i][j][0]=(dp[l&1][i-1][j][0]+dp[l&1][i-1][j][1])%mod;

            }

        if(l==2)

            for(int i=0;i<=n;i++)

                dp[0][i][0][0]=0;

    }

    printf("%d\n",(dp[k&1][n][m][0]+dp[k&1][n][m][1])%mod);

}

2018.6.10

相关文章