【模板】P1439 最长公共子序列
P1439 【模板】最长公共子序列（洛谷题面）
题目
题目描述：
给出 的两个排列 和 ，求它们的最长公共子序列。
输入格式：
第一行是一个数 。
接下来两行，每行为 个数，为自然数 的一个排列。
输出格式：
一个数，即最长公共子序列的长度。
数据范围与说明：
- 对于 的数据， ；
- 对于 的数据， 。
输入输出样例 #1
输入：
5
3 2 1 4 5
1 2 3 4 5
输出：
3
题意
给定 的两个排列 、，求它们的最长公共子序列（LCS）长度。
思路
经典做法是 动态规划，但对于 的数据会超时。利用“两个序列都是排列”的性质，可以将 LCS 转化为 LIS（最长上升子序列）：
- 建立哈希（或数组）
mp[val]记录值val在序列 中的位置； - 遍历 ，将 P_1$ 中的位置
mp[P2[i]]依次写入新数组； - 问题就变成了：求该新数组的 LIS 长度，使用
lower_bound+ 贪心即可达到 。
复杂度：时间 ，空间 。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int pos[N], b[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int v; cin >> v;
pos[v] = i;
}
for (int i = 1; i <= n; ++i) cin >> b[i];
vector<int> lis;
lis.reserve(n);
for (int i = 1; i <= n; ++i) {
int mapped = pos[b[i]];
auto it = lower_bound(lis.begin(), lis.end(), mapped);
if (it == lis.end()) lis.push_back(mapped);
else *it = mapped;
}
cout << lis.size() << '\n';
return 0;
}