luoguP2679 子串

个人感觉\(noip\)系列中挺好的一道DP题目.

题面有点难理解.

我们设\(f_{i,j,k,0/1}\)表示\(A\)串前\(i\)个字符,匹配\(B\)串前\(j\)个字符,正在用第\(k\)的子串,且第\(i\)个字符选或者不选的方案数

则有\(f_{i,j,k,0} = f_{i - 1,j,k,0} + f_{i - 1,j,k,1}\)

如果\(A_i == A_j\),那么有

\(f_{i,j,k,1} = f_{i - 1,j - 1,k - 1,1} + f_{i - 1,j - 1,k - 1,0}+f_{i - 1,j - 1,k,1}\)

否则

\(f_{i,j,k,1} = 0\)(因为无法匹配)

但是,空间复杂度不够优秀。

将第一维滚掉就好了

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e3 + 3;
const int M = 2e2 + 2;
const int mod = 1e9 + 7;
int f[2][M][M][2];
int n,m,kk;
char s1[N],s2[M];
int main(){
    scanf("%d%d%d",&n,&m,&kk);
    scanf("%s%s",s1 + 1,s2 + 1);
    int now = 0;
    f[1][0][0][0] = f[0][0][0][0] = 1;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j)
            for(int k = 1;k <= kk;++k){
                f[now][j][k][0] = (1ll * f[now ^ 1][j][k][0] + f[now ^ 1][j][k][1]) % mod;
                if(s1[i] == s2[j])
                f[now][j][k][1] = (1ll * f[now ^ 1][j - 1][k][1] 
                + f[now ^ 1][j - 1][k - 1][0] + f[now ^ 1][j - 1][k - 1][1]) % mod;
                else f[now][j][k][1] = 0;           
        }
        now ^= 1;
    }
    printf("%d\n",(f[now ^ 1][m][kk][0] + f[now ^ 1][m][kk][1]) % mod); 
    return 0;   
}

luoguP2679 子串

原文：https://www.cnblogs.com/wyxdrqc/p/10805977.html