NC19978 [HAOI2010]最长公共子序列

dp[i][j]的含义为s1串的前i长度与s2串的前j长度的最长公共子序列
res[i][j]的含义为s1串的前i长度与s2串的前j长度的最长公共子序列长度为dp[i][j]的数目
如果s1[i][j]==s2[i][j]那么dp[i][j]=dp[i-1][j-1]+1 res[i][j]=res[i-1][j-1]
如果不相等 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); 注意 dp[i][j - 1]和 dp[i - 1][j]都包含了dp[i-1][j-1]的情况，所以如果dp[i][j]==dp[i-1][j-1]，res[i][j]应该减去res[i-1][j-1]。

#include <iostream>
#include <string.h>
using namespace std;
const int maxn = 5010;
const int mod = 100000000;
int dp[maxn][maxn];
int res[maxn][maxn];
char s1[maxn];
char s2[maxn];
int main()
{

    cin >> s1+1 >> s2+1;
    int n = strlen(s1 + 1) - 1;
    int m = strlen(s2 + 1) - 1;
    for (int i = 0; i <= n; i++) res[i][0] = 1;
    for (int i = 0; i <= m; i++) res[0][i] = 1;

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i] == s2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                res[i][j] = res[i - 1][j - 1];

            }
            else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                if (dp[i][j] == dp[i - 1][j - 1])res[i][j] = (res[i][j] - res[i - 1][j - 1] + mod) % mod;
            }
            if (dp[i][j] == dp[i - 1][j]) res[i][j] += res[i - 1][j];
            if (dp[i][j] == dp[i][j - 1]) res[i][j] += res[i][j - 1];


            res[i][j] %= mod;
        }
    }
    cout << dp[n][m]<<endl;
    cout << res[n][m];
}