题解：P1439 【模板】最长公共子序列

Manchester_City_FC · 2025-03-09 15:03:08 · 题解

题目大意

给出 1,2,\ldots,n 的两个排列 P_1 和 P_2 ，求它们的最长公共子序列。

算法介绍

朴素解法

我们定义 dp_{i,j} 表示前 i 个元素的排列 P_1 和前 j 个元素的排列 P_2 的最长公共子序列的长度。状态转移方程如下：

• 如果 {P_1}_{i-1}={P_2}_{j-1}，则有：dp_{i,j}=dp_{i-1_j-1}+1。
• 否则 dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})。

这个 dp 的时间复杂度为 \mathcal O(n^2)，需要优化。

优化 dp

由于两个序列均为 1 到 n 的一个排列，每个数字均只出现一次，因此可以将其中一个排列映射为另一个排列中数字出现的位置。

假设有两个排列 A 和 B。首先利用 B 的排列建立一个映射：对于每个数字，记录该数字在 B 中的位置。接着，根据 A 中数字出现的顺序，将 A 中的每个数字转换为它在 B 中的位置。如此一来，我们得到一个新的序列 s，可以证明两个排列的公共子序列对应于新序列的递增子序列，而最长公共子序列的长度即为最长递增子序列的长度。

接下来求最长递增子序列（LIS）即可。

使用常见的二分查找方法，可以在 \mathcal O(n \log n) 的时间内求出 LIS 的长度。具体做法是维护一个数组 t，其长度表示当前找到的递增序列的长度，对于每一个元素：

• 如果该元素大于 t 数组的最后一个元素，则直接追加；
• 否则，二分查找找到 t 中第一个不小于该元素的位置，并更新该位置的值。

整体时间复杂度为 \mathcal O(n \log n)，可以通过本题。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,a[N],b[N],pos[N],s[N],t[N],ans;
//pos 记录数字在第二个排列中的位置（数字范围 1~n）
//t 数组：t[i] 表示长度为 i+1 的递增子序列末尾最小的值
//ans 为最长递增子序列的当前长度
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        cin>>b[i];
        pos[b[i]]=i;//建立映射
    }
    for(int i=0;i<n;i++) s[i]=pos[a[i]];
    for(int i=0;i<n;i++){
        if(!ans||s[i]>t[ans-1]) t[ans++] = s[i];//当前元素比所有尾部元素都大，直接追加
        else{
            //使用二分查找在 t 中寻找第一个大于等于 s[i] 的位置
            int l=0,r=ans-1;
            while(l<=r){
                int mid=l+(r-l)/2;
                if(t[mid]>=s[i]) r=mid-1;
                else l=mid+1;
            }
            t[l]=s[i];//更新找到的位置
        }
    }
    //输出最长公共子序列的长度，即为 LIS 的长度
    cout<<ans;
}