题目地址：洛谷：【P2516】[HAOI2010]最长公共子序列 – 洛谷、BZOJ：Problem 2423. — [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的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。

题意简述

求两个串LCS长度及个数。

输入输出格式

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

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

输入输出样例

输入样例#1：

ABCBDAB.
BACBBD.

输出样例#1：

4
7

题解

注意到本题卡空间，要用到滚动数组优化空间。
这里可以把统计方案数跟DP一起做，LCS依然是那个经典的DP问题，只不过这里把第一维给滚动掉了。至于方案数，检查该状态从哪些其他状态转移而来，加上这些状态的方案数即可。如果s1[i]!=s2[j]，且dp[i][j]==dp[i-1][j-1]，则要减去dp[i-1][j-1]对应的方案数，因为这个方案数会在dp[i][j-1]和dp[i-1][j]被计算两次，算重了。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

const int MAXN = 5005, MO = 1e8;

int n, m, dp[2][MAXN], dp2[2][MAXN];
char s1[MAXN], s2[MAXN];

int main() {
    scanf("%s%s", s1 + 1, s2 + 1);
    n = strlen(s1 + 1) - 1; m = strlen(s2 + 1) - 1;
    for(int i = 0; i <= m; i++) dp2[0][i] = 1;
    dp2[1][0] = 1;
    int p = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            dp[p][j] = std::max(dp[p ^ 1][j], dp[p][j - 1]);
            dp2[p][j] = 0;
            if(s1[i] == s2[j]) {
                dp[p][j] = std::max(dp[p][j], dp[p ^ 1][j - 1] + 1);
            }
            if(s1[i] == s2[j] && dp[p][j] == dp[p ^ 1][j - 1] + 1) {
                dp2[p][j] = (dp2[p][j] + dp2[p ^ 1][j - 1]) % MO;
            }
            if(dp[p][j] == dp[p ^ 1][j]) {
                dp2[p][j] = (dp2[p][j] + dp2[p ^ 1][j]) % MO;
            }
            if(dp[p][j] == dp[p][j - 1]) {
                dp2[p][j] = (dp2[p][j] + dp2[p][j - 1]) % MO;
            }
            if(dp[p][j] == dp[p ^ 1][j - 1]) {
                dp2[p][j] = ((dp2[p][j] - dp2[p ^ 1][j - 1]) % MO + MO) % MO;
            }
        }
        p ^= 1;
    }
    printf("%d\n%d", dp[p ^ 1][m], dp2[p ^ 1][m]);
    return 0;
}