$\color{#77E44C}{普及+/提高}$
题目描述
给出 $1,2,\ldots,n$ 的两个排列 $P_1$ 和 $P_2$ ,求它们的最长公共子序列。
输入格式
第一行是一个数 $n$。
接下来两行,每行为 $n$ 个数,为自然数 $1,2,\ldots,n$ 的一个排列。
输出格式
一个数,即最长公共子序列的长度。
样例输入 #1
5
3 2 1 4 5
1 2 3 4 5
样例输出 #1
3
提示
- 对于 $50\%$ 的数据, $n \le 10^3$;
- 对于 $100\%$ 的数据, $n \le 10^5$。
思路
这题充分诠释了如何将LCS
转化为LIS
问题
首先可以观察到数据范围,最多只能使用 $O(nlogn)$ 的方法解决,而LCS
时间复杂度为 $O(n^2)$, 只有LIS
拥有 $O(nlogn)$ 的二分优化
考虑将 LCS转化为LIS:
实际上样例已经给了一些提示,可以发现,如果第二行是有序 $1$ 到 $n$,那么对于第一行来说,只需要求上升子序列即可
但是问题在于,题目不能保证一定输入这样的序列,因此考虑自己动手 构造
这也是本题的最大难点:将第一行输入序列 重新映射 到 $1$ 到 $n$,那么第二行的权重就可以转化,转化后就是一个 LIS
问题
最后,采用二分法LIS
即可
c++代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int N = 100010;
int g[N], q[N];
int n, m;
pii mp[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
scanf("%d", &mp[i].first);
mp[mp[i].first].second = i;
}
for(int i = 1; i <= n; i ++)
{
scanf("%d", &g[i]);
g[i] = mp[g[i]].second;
}
int len = 0;
for(int i = 1; i <= n; i ++)
{
int idx = lower_bound(q + 1, q + len + 1, g[i]) - q;
q[idx] = g[i];
len = max(len, idx);
}
cout << len << endl;
return 0;
}