洛谷 2679 [NOIP 2015] 子串

给你两个字符串A,B从A中取出K个不重合子串（顺序与在A中顺序相同）组成B，问有多少种方案？

Solution

话说重打还是出各种错误也是醉了

先看题目，因为答案与A串，B串和拆分次数都有关，那么我们把这些都定义进DP方程中：

定义f[i][j][k][0]代表选到A串的前i个字符中选k个子串组成B[1-j]，且第i个不选。

那么f[i][j][k][1]就是代表选到A串的前i个字符中选k个子串组成B[1-j]，且第i个选。

定义好状态就很好做了：

如果这个不选，那么很明显就等于前一个选+不选，所以：

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

那么如果选呢？首先需要注意因为要选，所以需要A[i]==B[j]，否则不匹配。先看转移方程：

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

f[i-1][j-1][k][1]说明选i并且接在i-1后面组成一整个子串。

f[i-1][j-1][k-1][0] 因为i-1不选，所以需要从k-1转移过来。

f[i-1][j-1][k-1][1] i-1选了，i也可以单独组成子串。

注意事项：

1.因为模数是1e9+7，三个1e9+7就会爆int，所以第二个转移方程需要加两个模一下，再加第三个（WA了40分)。

2.如果直接定义f数组空间复杂度是 1000200200*2=8e7 超过了128MB，并且我们的转移方程中 i 的状态只与 i-1 有关，所以需要滚掉第一维。

Coding

#include<bits/stdc++.h>

using namespace std;

const int P = 1e9+7;

const int N = 205;

int t,n,m,f[2][N*5][N][2],K;

char A[N*5],B[N];

int main()

{

    cin>>n>>m>>K;

    scanf("%s",A+1);

    scanf("%s",B+1);

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

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

    {

        t=!t;f[t][0][0][0]=1;

        for(int j=1;j<=min(i,m);j++)

            for(int k=1;k<=min(j,K);k++)

                {

                    f[t][j][k][0]=(f[!t][j][k][0]+f[!t][j][k][1])%P;

                    if(A[i]==B[j])

                    {

                    	f[t][j][k][1]=(f[!t][j-1][k][1]+f[!t][j-1][k-1][0])%P;

                    	f[t][j][k][1]=(f[t][j][k][1]+f[!t][j-1][k-1][1])%P;

                    }

                    else f[t][j][k][1]=0;

                }

    }

    cout<<(f[t][m][K][1]+f[t][m][K][0])%P;

    return 0;

}

巴特西

洛谷 2679 [NOIP 2015] 子串

最新文章

热门文章