NOIP2015 子串

Description:

给定 \(A,B\) 两个字符串,把 \(A\) 串分成 \(k\) 个连续不交叉子串,求把所有字串按顺序排起来得到 \(B\) 串的方案数。

Solution:

设 \(f_{i,j,k,1/0}\) 表示 \(A_{1..i} , B_{1..j}\) 且子串数为 \(k\) 的方案数。

则:![]()

好像也可以设 \(f_{i,j,k,0}\) 表示选不选都行的方案数,同理方程就好推了qwq

然后滚动优化一下就好了。

(话说四维层面上的东西真是不好想

Code:

#include<bits/stdc++.h>
using namespace std;

const int N = 1e4;
const int M = 1e3;
const int mod = 1e9+7;
int n,m,K;
int f[M][M][2];
char a[N],b[N];

int main()
{
    scanf("%d%d%d\n",&n,&m,&K);
    gets(a+1);gets(b+1);
    f[0][0][0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=min(i,m);j>=1;--j)
        {
            for(int k=1;k<=min(j,K);++k)
            {
                if(a[i]==b[j])
                {
                    f[j][k][0]=(f[j][k][0]+f[j][k][1])%mod;
                    f[j][k][1]=((f[j-1][k-1][0]+f[j-1][k-1][1])%mod+f[j-1][k][1])%mod;//这里 % 一次导致调了1h-,真·细节决定成败。。。 
                }
                else if(a[i]!=b[j])
                {
                    f[j][k][0]=(f[j][k][0]+f[j][k][1])%mod;
                    f[j][k][1]=0;
                }
            }
        }
    }
    printf("%d\n",(f[m][K][0]+f[m][K][1])%mod);
    return 0;
}

Question:

dp的初值问题:比如这道题,为啥 \(f_{0,0,1}\not =1\) ?

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。