「Bzoj 2423」「HAOI2010」最长公共子序列 (DP最长公共子序列)

BZOJ 2423
题意：给定两个长度为$n, m$字符串, 求最长公共子序列长度和方案数$\mod 10^{8}$ $n,m\leq 5000$

第一问太简单不再说，主要看第二问
对于第二问，我们当前第一问的 DP 状态是 $ dp(i, j) $ 表示第一个串匹配到 $ i $，第二个串匹配到 $ j $ 的最长公共子序列。
然后我们再加一个数组 $ g(i, j) $ 表示第一个串匹配到 $ i $，第二个串匹配到 $ j $ 的最长公共子序列方案数。
对于这个数组的转移：
当 $ a_i = b_j $ 时，方案数加上$ g(i-1,j-1) $ 如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $，那么加上这些方案数
否则如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $，那么加上这些方案数。但是如果当前还等于 $ dp(i-1, j-1) $，说明 $ a_i , b_j $ 没做贡献，说明两个 LCS 均是从$i-1,j-1$的位置转移而来，减掉$ g(i-1,j-1) $即可。

知识点：
1、看限制开数组，不要爆空间
2、方案数可以用容斥的方法来求

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MO = 100000000, MAXN = 5000 + 5;

    int la, lb, dp[2][MAXN], g[2][MAXN];
    char a[MAXN], b[MAXN];

    void clean() {
        ms(dp, 0);
    }
    int solve() {
        scanf("%s%s", a + 1, b + 1);
        clean();
        la = strlen(a + 1) - 1, lb = strlen(b + 1) - 1;
        int cur = 0;
        for (int i = 0; i <= lb; ++i) g[cur ^ 1][i] = 1;
        for (int i = 1; i <= la; ++i) {
            for (int j = 0; j <= lb; ++j) dp[cur][j] = 0, g[cur][j] = 0;
            g[cur][0] = 1;
            for (int j = 1; j <= lb; ++j) {
                dp[cur][j] = max(dp[cur ^ 1][j], dp[cur][j - 1]);
                if (a[i] == b[j]) {
                    dp[cur][j] = dp[cur ^ 1][j - 1] + 1;
                    g[cur][j] = g[cur ^ 1][j - 1];
                    if (dp[cur][j] == dp[cur ^ 1][j]) g[cur][j] = (g[cur][j] + g[cur ^ 1][j]) % MO;
                    if (dp[cur][j] == dp[cur][j - 1]) g[cur][j] = (g[cur][j] + g[cur][j - 1]) % MO;
                } else {
                    if (dp[cur][j] == dp[cur ^ 1][j]) g[cur][j] = (g[cur][j] + g[cur ^ 1][j]) % MO;
                    if (dp[cur][j] == dp[cur][j - 1]) g[cur][j] = (g[cur][j] + g[cur][j - 1]) % MO;
                    if (dp[cur][j] == dp[cur ^ 1][j - 1]) g[cur][j] = (g[cur][j] - g[cur ^ 1][j - 1] + MO) % MO;
                }
            }
            cur ^= 1;
        }
        printf("%d\n%d\n", dp[cur ^ 1][lb], g[cur ^ 1][lb]);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}