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

· · 个人记录

1.题意简述

给定两个字符串 a 和 b，求这两个串的最长公共子序列长度，以及 a 和 b 的所有公共子序列中长度为该长度的方案数。

2.前置知识

最长公共子序列，即 LCS，是指对于两个字符串，使这两个字符串各删除若干个元素后相等，求最后这个相等的子序列长度。

举个例子，对于字符串 ABICPD 和 AMBCD，将第一个字符串删除两个元素后，得到 ABCD，第二个字符串删除一个元素后，得到 ABCD，删除后两个字符串相等且最长，所以这两个字符串的 LCS 长度为 4。

对于这个问题，可以用动态规划解决，定义 dp_{i,j} 为字符串 a 的前 i 个元素与字符串 b 的前 j 个元素的 LCS 长度。

得到状态转移方程：

3.题目做法

这题第一问比较基础，第二问难度比较大，我们不妨像 LCS 一样，先定义 cnt_{i,j} 表示字符串 a 的前 i 个元素与字符串 b 的前 j 个元素的方案数。

然后我们再思考如何状态转移 cnt_{i,j}，其实就以下几种情况：

当 a_i=b_j 时，cnt_{i,j}\gets cnt_{i,j}+cnt_{i-1,j-1}，即情况一。

当 dp_{i,j}=dp_{i,j-1} 时，cnt_{i,j}\gets cnt_{i,j}+cnt_{i,j-1}，即情况二和四。

当 dp_{i,j}=dp_{i-1,j} 时，cnt_{i,j}\gets cnt_{i,j}+cnt_{i-1,j}，即情况三和四。

当 a_i\neq b_j 且 dp_{i,j-1}=dp_{i-1,j} 时，说明上述情况二和四与情况三和四同时满足，说明 cnt_{i,j} 多加了，所以 cnt_{i,j}\gets cnt_{i,j}-cnt_{i,j-1}。

写完这些，就能过样例了，但是仍可以优化，可以使用滚动数组将 i-1 替换成 t^1，可以将原本平方级别的空间复杂度，压缩成线性。

还有，别忘了对 10^8 取模。

4.代码实现

通过记录

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e8;
string a,b;
int l1,l2;
int dp[2][5005];
int cnt[2][5005];
int t;
int main(){
    cin>>a>>b;
    l1=a.length()-1;
    l2=b.length()-1;
    for(int i=0;i<=l2;i++)cnt[0][i]=1;
    cnt[1][0]=1;
    for(int i=1;i<=l1;i++,t=t^1){
        for(int j=1;j<=l2;j++){ 
            cnt[t^1][j]=0;
            if(a[i-1]==b[j-1]){
                dp[t^1][j]=dp[t][j-1]+1;
                cnt[t^1][j]+=cnt[t][j-1];
            }else{
                dp[t^1][j]=max(dp[t][j],dp[t^1][j-1]);
            }
            if(dp[t^1][j]==dp[t^1][j-1]){
                cnt[t^1][j]+=cnt[t^1][j-1];
            }
            if(dp[t^1][j]==dp[t][j]){
                cnt[t^1][j]+=cnt[t][j];
            }
            if(a[i-1]!=b[j-1]&&dp[t^1][j]==dp[t][j-1]){
                cnt[t^1][j]-=cnt[t][j-1];
            }
            cnt[t^1][j]%=MOD;
        }
    }
    cout<<dp[t][l2]<<endl<<(cnt[t][l2]%MOD)<<endl;
    return 0;
}