B1822 最长公共子序列2
大约 2 分钟动态规划
B1822 最长公共子序列2
【算法标签】 动态规划、最长公共子序列(LCS)、最长上升子序列(LIS)
【语法标签】 :数组、for循环、二分查找、upper_bound
给定两个长度为 n 的排列 P1 和 P2(元素均为 1~n 且不重复),求它们的最长公共子序列(LCS)的长度。
注意:常规的 LCS 算法无法通过本题(n 最大可达 ),需要利用排列的特殊性质优化。
二、解题思路
核心转化:LCS → LIS
对于两个排列,它们的最长公共子序列问题可以转化为最长上升子序列(LIS)问题,从而将时间复杂度从 降至 。
转化原理:
建立映射关系:
对于排列
P1,我们记录每个数字x在P1中的位置pos[x]。例如:
P1 = [3,2,1,4,5],则pos[3]=1,pos[2]=2,pos[1]=3,pos[4]=4,pos[5]=5。重排
P2:用上述映射关系,将
P2中的每个元素b[i]替换为它在P1中的位置pos[b[i]],得到新数组d。例如:
P2 = [1,2,3,4,5],则d = [pos[1], pos[2], pos[3], pos[4], pos[5]] = [3,2,1,4,5]。关键结论:
P1和P2的最长公共子序列长度,等于数组d的最长上升子序列(LIS)长度。因为
d中的元素代表了P2中元素在P1中的出现位置,一个 “上升的子序列” 意味着这些元素在P1中也是按顺序出现的,因此它们是两个排列的公共子序列。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], pos[N], d[N], dp[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// 步骤1:记录a数组中每个元素的位置
for (int i = 1; i <= n; i++) {
cin >> a[i];
pos[a[i]] = i;
}
// 步骤2:将b数组映射为位置数组d
for (int i = 1; i <= n; i++) {
cin >> b[i];
d[i] = pos[b[i]];
}
// 步骤3:用二分优化的LIS算法求d的最长上升子序列
dp[1] = d[1];
int len = 1;
for (int i = 2; i <= n; i++) {
if (d[i] >= dp[len]) {
// 可以直接接在当前最长上升子序列后面
len++;
dp[len] = d[i];
} else {
// 找到dp中第一个大于等于d[i]的位置并替换
/*
int k = upper_bound(dp+1,dp+len+1, dp[i]) - dp;
dp[k] = d[i];
*/
int l = 1, r = len;
while (l <= r) {
int mid = (l + r) / 2;
if (d[i] <= dp[mid])
r = mid - 1;
else
l = mid + 1;
}
dp[l] = d[i];
}
}
cout << len << endl;
return 0;
}