最长公共子序列

第一个问题应该都是会的，主要分析第二问。
定义 $g[i][j]$ 表示 $f[i][j]$ 对应的状态长度等于 $f[i][j]$ 的公共子序列的数量。
1.如果 $A[i]==B[j]$ ，则表示可以由 $g[i-1][j-1]$ 推出。
2.如果 $f[i][j]==f[i][j-1]$ ，则表示可以由 $g[i][j-1]$ 推出。
3.如果 $f[i][j]==f[i-1][j]$ ，则表示可以由 $g[i-1][j]$ 推出。
4.如果 $A[i]!=B[j] \&\& f[i][j]==f[i-1][j-1]$ ，那么 $f[i][j]=f[i-1][j]==f[i][j-1]==f[i-1][j-1]$ ，即2、3都会满足，并且 $f[i][j-1]、f[i-1][j]$ 都包含 $f[i-1][j-1]$ ，所以此时需要减去一个 $f[i-1][j-1]$ 。

还需要滚动数组。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7, mod = 1e8;
int f[2][5005];
ll g[2][5005];
char A[5005],B[5005];
int main() {
    scanf("%s%s",A+1,B+1);
    int n=strlen(A+1)-1,m=strlen(B+1)-1;
    for(int i = 1; i <= m; i++) g[0][i] = 1; g[0][0] = g[1][0] = 1;
    int cur(0);
    for(int i=1;i<=n;++i) {
        cur^=1;
        for(int j=1;j<=m;++j) {
            g[cur][j] = 0;
            if(A[i]==B[j]) {
                f[cur][j]=f[cur^1][j-1]+1;
                g[cur][j]=g[cur^1][j-1];
            }
            else {
                f[cur][j]=max(f[cur][j-1],f[cur^1][j]);
                if(f[cur][j]==f[cur^1][j-1])
                    g[cur][j]=mod-g[cur^1][j-1];
            }
            if(f[cur][j]==f[cur][j-1]) g[cur][j]+=g[cur][j-1];
            if(f[cur][j]==f[cur^1][j]) g[cur][j]+=g[cur^1][j];
            g[cur][j]%=mod;
        }
    }
    printf("%d\n",f[cur][m]);
    printf("%d\n",g[cur][m]);
    return 0;
}