【NOIP2015】子串（动态规划）

题目戳我

题解

很简单的一道题。。。

看来那时候还是我太菜了。。。

设f[i][j][k][0/1]表示在第一个串中的位置i，匹配到了位置j，一共分了k段，0/1表示上一个位置是否在某一段中

转移就很简单了呀。。。。

如果能够匹配上（不能够匹配上直接复制状态就行了。。。）

自己YY一下转移就行了。。。

因为数组开不下，所以要滚掉一维数组。。。

真心大水题。。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MOD 1000000007

#define MAX 2000

char s1[MAX],s2[MAX];

//f[i][j][k][0/1]表示当前在第i个位置，匹配到了第j个位置，已经分了k段，是否在段中

int n,m,K;

int f[2][301][301][2];

int main()

{

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

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

    f[0][0][0][0]=1;

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

    {

        f[i&1][0][0][0]=1;

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

        {

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

            {

                f[i&1][j][k][0]=f[i&1][j][k][1]=0;

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

                {

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

                    f[i&1][j][k][1]%=MOD;

                    f[i&1][j][k][1]+=f[(i+1)&1][j-1][k-1][0];

                    f[i&1][j][k][1]%=MOD;

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

                    f[i&1][j][k][1]%=MOD;

                }

                f[i&1][j][k][0]+=f[(i+1)&1][j][k][0];

                f[i&1][j][k][0]%=MOD;

                f[i&1][j][k][0]+=f[(i+1)&1][j][k][1];

                f[i&1][j][k][0]%=MOD;

            }

        }

    }

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

    return 0;

}