最长公共子序列
题目描述
出两个长度为 $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
思路
最长上升子序列
将最长公共子序列问题转化为最长上升子序列问题,因为其中有一个序列是不重复的,也就是每个元素都唯一,只要将其中的数转化为下标映射,然后对于另一个数组b来说,首先找到在a数组中的下标,然后求出最长上升子序列的长度
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int q[N], idx[N];
int main()
{
int n;
scanf("%d",&n);
memset(idx,-1,sizeof idx);
for(int i = 0;i < n;i ++)
{
int x;
scanf("%d",&x);
idx[x] = i;
}
q[0] = -1;
int tt = 0;
for(int i = 0;i < n;i ++)
{
int x;
scanf("%d",&x);
int k = idx[x];
if(k == -1) continue;
int l = 0, r = tt;
// 找到小于k的最大数
while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] < k) l = mid;
else r = mid - 1;
}
q[r + 1] = k;
tt = max(tt, r +1);
}
printf("%d\n",tt);
return 0;
}