题目描述
给出两个长度为 n 的整数序列,求它们的最长公共子序列(LCS)的长度,保证第一个序列中所有元素都不重复。
注意:
第一个序列中的所有元素均不重复。
第二个序列中可能有重复元素。
一个序列中的某些元素可能不在另一个序列中出现。
输入格式
第一行包含一个整数 n。
接下来两行,每行包含 n 个整数,表示一个整数序列。
输出格式
输出一个整数,表示最长公共子序列的长度。
数据范围
$1≤n≤10^6$,
序列内元素取值范围 $[1,10^6]$。
样例
输入样例1:
5
1 2 3 4 5
1 2 3 4 5
输出样例1:
5
输入样例2:
5
1 2 3 5 4
1 2 3 4 5
输出样例2:
4
等价转换,最长上升子序列2(算法基础课)
(优化后的最长上升子序列) $O(nlogn)$
题目中最重要的提示:
第一个序列中的所有元素均不重复
也就是说,在第一个序列中出现的所有元素都是唯一的。
最长公共子序列的经典思路是比较最后一个元素是否相等
因为第二个数组中的元素如果在第一个数组中有相同的元素,那他在第一个数组中对应的元素下标一定唯一不变
故可以将两个数组的最长公共子序列问题转化成最长上升子序列。
Why
因为子序列的定义是,组成子序列的元素在原数组的下标一定是严格单调递增的。
所以我们可以将两个数组转换成一个下标数组,借助辅助数组来保存第一个数组各元素的下标。
再通过第二个数组中的元素对应的下标,组成我们的下标数组。
之后就可以用基础课里讲的nlogn的最长上升子序列解法啦
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],b[N],idx[N];
vector<int> aa;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
idx[a[i]]=i;
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
b[i]=idx[b[i]];
}
for(int i=1;i<=n;i++){
if(b[i]==0) continue;
if(!aa.size()||b[i]>aa.back()) aa.push_back(b[i]);
int id=lower_bound(aa.begin(),aa.end(),b[i])-aa.begin();
aa[id]=b[i];
}
cout<<aa.size();
return 0;
}
这两步太漂亮了吧,我还想去查找嘞,这样一翻转就解决了,降维打击可谓是。
大佬,这里的下标数组是指 B序列的第几个元素,在A 序列中的下标吧。
也即 下标数组[ B序列中该元素的下标 ] =A 序列中该元素的下标
下标也就是位置。
对
TLE了?
1e^6的输入,得用scanf,不能用cin
是了
“将两个数组转换成一个下标数组,借助辅助数组来保存第一个数组各元素的下标。
再通过第二个数组中的元素对应的下标,组成我们的下标数组。”
大佬,这个地方可以再解释一下吗?我模拟完数据还是不太理解
下标数组中存的是按顺序扫描第二个数组中每个元素在第一个数组中出现的位置
谢谢啦!
1e6为啥nlogn可以过
log1e6大概只有20
哦哦,感谢