NOIP2015Day2T2子串(字符串dp)

　　又被“if(a=b)”坑了QAQ。。。写C++还是得开Warning，这么久了pascal还没改过来咋回事啊QWQ

　　题目大意就不说了OWO

　　网上的题解都不怎么看得懂啊。。。好像写得都很乱？还是我太sb了

　　f[i][j][k][0]表示A串前i个字符和B串前j个字符能够匹配，并且分成k段，a[i]不选。f[i][j][k][1]同理但a[i]要选。

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

　　　　　　　if(a[i]==b[j])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];

　　①第一维滚动②快速取模

　　字符串DP真的是我非常非常薄弱的一部分了，连状态设计都想了很久很久。。。

代码如下：

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#define min(x,y) (x<y?x:y)

#define MOD(x) (x>=mod?x-mod:x)

using namespace std;

const int maxn=,mod=1e9+;

int n,m,K;

int f[][][][];

char s1[maxn],s2[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(m);read(K);

    scanf("%s",s1+);scanf("%s",s2+);

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

    {

        f[][][][]=f[][][][]=;

        int up=min(i,m);

        for(int j=;j<=up;j++)

        {

            for(int k=;k<=K;k++)

            {

                if(s1[i]==s2[j])

                f[i&][j][k][]=MOD(MOD(f[(i&)^][j-][k][]+f[(i&)^][j-][k-][])+f[(i&)^][j-][k-][]);

                else f[i&][j][k][]=;

                if(j<i)f[i&][j][k][]=MOD(f[(i&)^][j][k][]+f[(i&)^][j][k][]);

                else f[i&][j][k][]=;

            }

        }

    }

    printf("%d",MOD(f[n&][m][K][]+f[n&][m][K][]));

}

巴特西

NOIP2015Day2T2子串(字符串dp)

最新文章

热门文章