Luogu2679 子串

发布于 2020-09-03  48 次阅读


Link

不得不说中考之后水平极度降低了

设计状态

显然想要DP我们必须要枚举比较的A\B串的位置,以及当前划分到第k个子串的方案数

我们可以直接设f[i][j][k]表示A串的前i个字符匹配了B串的前j个字符,已经划分到了第k个串

A串中的字符对每一种方案都有两种状态,选or不选

那么我们设f[i][j][k][0/1]表示A串的前i个字符匹配了B串的前j个字符,已经划分到了第k个串,1表示选第i+1个字符,0反之

转移需要分情况讨论(为了方便下面还是用i表示当前A串字符)

a[i]==b[j]

如果我们不选这个字符,那么f[i][j][k][0] = f[i - 1][j][k][0] + f[i - 1][j][k][1]

解释:当前字符不选,但是上一位的答案仍然可能可以更新下一位,那么到当前字符位置,方案数便是前一位选或不选的和

如果选择这个字符,那么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]

解释:按照顺序解释,选择当前字符的方案书相当于(前一位已经被选中了,当前字符作为一个新子串)+(前一位没有选中,当前字符作为新的子串)+(前一位选中了,当前位与它一起算作一个子串)

a[i]!=b[j]
不选的方案数同上方法计算
选择的方案因为本来就选不了就直接=0

接下来考虑时间复杂度$4 \ 10^7显然时可以接受的
但是关于空间复杂度
8\
10^{7}$
它死了

然后这道题还可以顺便练习DP空间常用优化方法滚动数组(话说去年联赛我就是D2T1没有滚一维然后没有计算空间导致MLE直接80->0
所以一定要记得检查时空复杂度可行性

关于当前枚举A的每一位
每次更新答案都只需要用到ii-1
所以直接滚掉第一维
现在的空间是1.6\ *10^5
可以接受

代码方便大家贴一下

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

const int SIZE = 1000 + 5;
const int SIZE_K = 200 + 5;
const int Mod = 1000000007;

int n, m, k;
int f[2][SIZE_K][SIZE_K][2]; // f[i][j][k][0/1]
char a[SIZE], b[SIZE_K];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    scanf("%s%s", a + 1, b + 1);
    f[0][0][0][0] = f[1][0][0][0] = 1;
    int opt = 1;
    for (int i = 1; i <= n; i ++, opt ^= 1) {
        for (int j = 1; j <= m; j++) {
            for (int d = 1; d <= k; d++) {
                if (a[i] == b[j]) {
                    f[opt][j][d][0] = (f[opt ^ 1][j][d][0] + f[opt ^ 1][j][d][1]) % Mod;
                    f[opt][j][d][1] = (f[opt ^ 1][j - 1][d][1] + (f[opt ^ 1][j - 1][d - 1][1] + f[opt ^ 1][j - 1][d - 1][0]) % Mod) % Mod;
                }
                else {
                    f[opt][j][d][0] = (f[opt ^ 1][j][d][0] + f[opt ^ 1][j][d][1]) % Mod;
                    f[opt][j][d][1] = 0;
                }
            }
        }
    }
    printf("%d", (f[n & 1][m][k][1] + f[n & 1][m][k][0]) % Mod);
    return 0;
}

朴实沉毅