P2516 [HAOI2010]最长公共子序列 P2516 [HAOI2010]最长公共子序列

匹配DP。

最长公共子序列比较好求：

if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
else f[i][j] = max(f[i][j], max(f[i - 1][j], f[i][j - 1]));

那最长公共子序列的个数怎么求呢？

我们用(g[i][j])表示A串匹配到(i)，B串匹配到(j)的最长上升子序列的个数。

if(a[i] == b[j]) {
	g[i][j] = g[i - 1][j - 1];
    if(f[i][j] == f[i - 1][j]) g[i][j] += g[i - 1][j];
    if(f[i][j] == f[i][j - 1]) g[i][j] += g[i][j - 1];
    //f[i][j]肯定不等于f[i - 1][j - 1];
}
else {
	g[i][j] = 0;
    if(f[i][j] == f[i - 1][j]) g[i][j] += g[i - 1][j];
    if(f[i][j] == f[i][j - 1]) g[i][j] += g[i][j - 1];
    if(f[i][j] == f[i - 1][j - 1]) g[i][j] -= g[i - 1][j - 1];
    //如果第三个if成立，那么第一个和第二个if也肯定成立，那就会多算了一部分，我们只需要把多算的那一部分减去就好了
}

记得用滚动数组。

完整代码：

#include <bits/stdc++.h>
    
using namespace std;
    
inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}
    
const int N = 100005, mod = 100000000;
char cha[N], chb[N];
int lena, lenb, f[2][N], g[2][N];

int main() {

    cin >> cha + 1; cin >> chb + 1;
    lena = strlen(cha + 1) - 1;
    lenb = strlen(chb + 1) - 1;

    for(int i = 0;i <= lenb; i++) g[0][i] = 1;
    g[1][0] = 1;
    for(int i = 1;i <= lena; i++) {
        int tmp = i & 1;
        for(int j = 1;j <= lenb; j++) 
            if(cha[i] == chb[j]) {
                f[tmp][j] = max(f[tmp][j], f[tmp ^ 1][j - 1] + 1);
                g[tmp][j] = g[tmp ^ 1][j - 1];
                if(f[tmp][j] == f[tmp ^ 1][j]) (g[tmp][j] += g[tmp ^ 1][j]) %= mod;
                if(f[tmp][j] == f[tmp][j - 1]) (g[tmp][j] += g[tmp][j - 1]) %= mod;
            }
            else {
                f[tmp][j] = max(f[tmp][j], max(f[tmp ^ 1][j], f[tmp][j - 1]));
                g[tmp][j] = 0;
                if(f[tmp][j] == f[tmp ^ 1][j]) (g[tmp][j] += g[tmp ^ 1][j]) %= mod;
                if(f[tmp][j] == f[tmp][j - 1]) (g[tmp][j] += g[tmp][j - 1]) %= mod;
                if(f[tmp][j] == f[tmp ^ 1][j - 1]) (g[tmp][j] -= g[tmp ^ 1][j - 1]) %= mod;
            }
    }

    printf("%d
%d", f[lena & 1][lenb], (g[lena & 1][lenb] + mod) % mod);
    	
    return 0;
}

P2516 [HAOI2010]最长公共子序列 P2516 [HAOI2010]最长公共子序列

相关推荐