比较基础的一道 DP。

定义状态为 $f[i][j][k][0/1]$ 表示串 s 的前 $i$ 位,匹配了串 t 的前 $j$ 位,用了 $k$ 段,当前串 s 的第 $i$ 位是否被匹配(0/1)的方案数。

初始状态为 $f[0][0][0][0]=1$。

考虑用刷表法来转移,这样只需要考虑下一步的状态即可。

  • 如果不匹配,那么 $\texttt{f[i+1][j][k][0]+=f[i][j][p][0]+f[i][j][p][1]}$
  • 如果可以匹配,那么 $\texttt{f[i+1][j+1][k][1]+=f[i][j][k][0]}$ 和 $\texttt{f[i+1][j+1][k+1][1]+=f[i][j][k][0]+f[i][j][k][1]}$。

考虑到内存限制比较紧张,且每次转移只和下一个状态有关,考虑用滚动数组来优化空间。

时间复杂度 $\mathcal{O(n\log n)}$

/*
 * Author: chhokmah
 * Date: 2020-09-05
 */
#include <bits/stdc++.h>

using namespace std;

const int P = 1000000007;
const int N = 1005, M = 205;

int add(int x, int y, int mod = P) { return (x += y) >= mod ? x - mod : x; }
int sub(int x, int y, int mod = P) { return (x -= y) < 0 ? x += mod : x; }

int n, m, k;
char s[N], t[M];
int f[2][M][M][2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k >> (s + 1) >> (t + 1);
    f[0][0][0][0] = 1;
    for (int i = 0; i <= n; i++) {
        memset(f[i & 1 ^ 1], 0, sizeof f[i & 1 ^ 1]);
        for (int j = 0; j <= min(i, m); j++) {
            for (int p = 0; p <= min(i, k); p++) {
                f[i & 1 ^ 1][j][p][0] = add(f[i & 1 ^ 1][j][p][0], add(f[i & 1][j][p][0], f[i & 1][j][p][1]));
                if (s[i + 1] == t[j + 1]) {
                    f[i & 1 ^ 1][j + 1][p][1] = add(f[i & 1 ^ 1][j + 1][p][1], f[i & 1][j][p][1]);
                    f[i & 1 ^ 1][j + 1][p + 1][1] = add(f[i & 1 ^ 1][j + 1][p + 1][1], add(f[i & 1][j][p][0], f[i & 1][j][p][1]));
                }
            }
        }
    }
    cout << add(f[n & 1][m][k][0], f[n & 1][m][k][1]) << '\n';
    return 0;
}
最后修改:2020 年 09 月 06 日 03 : 41 PM
如果觉得我的文章对你有用,请随意赞赏