题解 洛谷P2516 [HAOI2010]最长公共子序列

Author Avatar
2U Aug 12, 2019
  • Read this article on other devices

题目描述

字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列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("%lld\n%lld\n", f[k][m], g[k][m]);
    return 0;
}

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Link to this article: https://www.singularity2u.top/2019/08/12/题解-洛谷P2516-HAOI2010-最长公共子序列/