题解 洛谷p2516 [haoi2010]最长公共子序列

字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij = yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。

第1行为第1个字符序列，都是大写字母组成，以”.”结束。长度小于5000。

第2行为第2个字符序列，都是大写字母组成，以”.”结束，长度小于5000。

第1行输出上述两个最长公共子序列的长度。

第2行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对100,000,000求余即可。

输入 #1

ABCBDAB.
BACBBD.

输出 #1

4
7

这是我在洛谷上AC的第二道紫题Orz，听了队友涵哥的讲解我对这题的递推过程颇有感触，特此给出详细解析。

a、b两个字符串的最长公共子序列的长度是唯一的，但最长公共子序列不是唯一的。

用f[i][j]表示a的前i位字符子串和b的前j位字符子串的最长公共子序列（下称lcm(i, j)）的长度，g[i][j]表示lcm(i, j)的种数。

要求最长公共子序列的长度并不难，易知状态转移方程为：f[i][j] = i == j ? f[i][j] = a[i] == b[j] ? f[i - 1][j - 1] + 1 : max(f[i - 1][j], f[i][j - 1])。

要求最长公共子序列的种数，可以给每个状态下的情况分类讨论：

①a[i]和b[j]都属于所有的lcm(i, j)。

②a[i]属于所有的lcm(i, j)，b[j]并非属于所有的lcm(i, j)。

③a[i]并非属于所有的lcm(i, j)，b[j]属于所有的lcm(i, j)。

④a[i]和b[j]都并非属于所有的lcm(i, j)。

若a[i] = b[j]，则f[i][j] = f[i - 1][j - 1] + 1，对应情况①。

若f[i][j] = f[i][j - 1]，则b[j]并非属于所有的lcm(i, j)（可根据逆否命题推断），对应的情况包括②④。

若f[i - 1][j] = f[i][j]，则a[i]并非属于所有的lcm(i, j)（可根据逆否命题推断），对应的情况包括③④。

若f[i][j] = f[i - 1][j - 1]，则对应情况④，并且此时也必满足其上两种的条件。

以上4种条件的结论涵盖各种情况，综上有：

if (a[i] == b[j]) g[i][j] += g[i - 1][j - 1]

if (f[i][j] == f[i][j - 1]) g[i][j] += g[i][j - 1]

if (f[i][j] == f[i - 1][j]) g[i][j] += g[i - 1][j]

if (f[i][j] == f[i - 1][j - 1]) g[i][j] -= g[i - 1][j - 1]（容斥原理）

滚动数组优化，k表示i状态，k ^ 1表示i - 1状态。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5e3 + 10, mod = 1e8;
int n, m, k;
char ch, a[maxn], b[maxn];
ll f[2][maxn], g[2][maxn];

int main()
{
    for (int i = 1; (ch = getchar()) != '.'; a[i] = ch, n = i, i++) ;
    getchar();
    for (int i = 1; (ch = getchar()) != '.'; b[i] = ch, m = i, i++) ;
    for (int i = 0; i <= m; i++) g[0][i] = 1; g[1][0] = 1;
    for (int i = 1; i <= n; i++, k ^= 1)
    {
        for (int j = 1; j <= m; j++)
        {
            g[k ^ 1][j] = 0;
            f[k ^ 1][j] = a[i] == b[j] ? f[k][j - 1] + 1 : max(f[k][j], f[k ^ 1][j - 1]);
            if (a[i] == b[j]) g[k ^ 1][j] += g[k][j - 1];
            if (f[k ^ 1][j] == f[k ^ 1][j - 1]) g[k ^ 1][j] += g[k ^ 1][j - 1];
            if (f[k ^ 1][j] == f[k][j]) g[k ^ 1][j] += g[k][j];
            if (f[k ^ 1][j] == f[k][j - 1]) g[k ^ 1][j] -= g[k][j - 1];
            g[k ^ 1][j] %= mod;
        }
    }
    printf("%lldn%lldn", f[k][m], g[k][m]);
    return 0;
}