题目描述(上交考研机试题)
给出两个长度为 n 的整数序列,求它们的最长公共子序列(LCS)的长度,保证第一个序列中所有元素都不重复。
注意:
1. 第一个序列中的所有元素均不重复。
2. 第二个序列中可能有重复元素。
3. 一个序列中的某些元素可能不在另一个序列中出现。
样例
输入样例
5 //两序列的长度
1 2 3 4 5 //序列1,此序列中每个元素都不重复;
1 2 3 4 5 //序列2,此序列可能重复,也可能有元素不在序列1中;
输出样例
4 //输出最长公共子序列长度;
数据范围
1≤n≤10^6 ,
序列内元素取值范围 [1,10^6]。
解题思路
贪心 $O(nlogn)$
求最长公共序列问题可以使用dp(T895)来做,但是时间复杂度为O(n^2),对于10^6数据量来说超时,故将其转化为最长上升子序列问题,则可以达到O(nlogn)的时间复杂度;
Tips
-
如何转化为最长上升子序列问题: 因为第一个序列中没有重复元素,则可知每一个元素与其下标是一一对应的,则可以有一个哈希数组将第一个序列 a 的数值与其下标做一个反向映射,再对第二个序列 b 根据此映射数组进行处理得到第二个序列与第一个序列的下标对应关系,则如果对公共子序列来说,在这个数组中是单调递增的,故转化为了最长上升子序列问题;
-
最长公共序列问题转化为最长上升子序列问题的条件是什么:
两个序列中至少有一个序列是没有重复元素的; -
在下面代码中哪个是转化后的最长上升子序列问题的序列:
在下面代码中,这个序列是隐含的,下面两个数组中,idx[]
存的是第一个序列的值与下标的映射,q[]
中存的是最长i
的子序列的最小末尾值;转化后的序列是一个一个经过处理过后的k值,准确来说,是i
为下标k
为数值的这么一个隐藏的数组; -
对于每一个
k
, 如果大于q[t]
(下标从0开始,t+1
长度的最长上升子序列,末尾最小的数字),那就使最长上升序列长度+1,当前末尾最小元素为k
。 若k
小于等于f[t]
,说明不会更新当前的长度,但之前末尾的最小元素要发生变化,找到第一个大于或等于k
的位置,更新以那时候末尾的最小元素。
#include<iostream>
using namespace std;
const int N = 1e6+7;
int idx[N], q[N];
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i = 1; i <= n; ++i){
int x;
cin>>x;
idx[x] = i; //对第一个序列进行的处理,将其转化为值与下标的映射;
}
int t = 0; //t为最长长度;
for(int i = 0; i < n; ++i){
int x;
cin>>x;
int k = idx[x]; //对第二个序列的每一个元素,找到它在第一个序列的下标,令为k;
if(k == 0) continue; //如果不在第一个序列中,则跳过;
int l = 0, r = t;
while(l < r){ //二分查找找到q[]中第一个不小于k的位置;
int mid = l + r >> 1;
if(q[mid] >= k) r = mid;
else l = mid + 1;
}
q[r] = k; //更新这个长度下最小的值;
if(t < r+1) t = r+1;
}
cout<<t;
return 0;
}