【题目来源】
洛谷：P1439 【模板】最长公共子序列 - 洛谷
【题目描述】
给出 \(1,2,\dots,n\) 的两个排列 \(P_1\) 和 \(P_2\) ，求它们的最长公共子序列。
【输入】
第一行是一个数 \(n\)。
接下来两行，每行为 \(n\) 个数，为自然数 \(1,2,\dots,n\) 的一个排列。
【输出】
一个数，即最长公共子序列的长度。
【输入样例】
5
3 2 1 4 5
1 2 3 4 5
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P1439 最长公共子序列》 #动态规划,dp# #二分#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100005; // 定义最大数组长度int n; // 数组长度
int a[N], b[N]; // 输入的两个数组
int m[N]; // 记录a数组中每个值对应的位置
set<int> dp; // 使用set维护最长递增子序列
set<int>::iterator it; // set的迭代器int main()
{// 输入数组长度cin >> n;// 输入数组a并记录每个数字的位置for (int i = 1; i <= n; i++) {cin >> a[i];m[a[i]] = i; // 记录数字a[i]在a数组中的位置}// 输入数组bfor (int i = 1; i <= n; i++) {cin >> b[i];}// 初始化dp集合，插入第一个元素在a中的位置dp.insert(m[b[1]]);// 处理数组b的剩余元素for (int i = 2; i <= n; i++) {// 在dp中查找第一个不小于当前元素位置的元素it = dp.lower_bound(m[b[i]]);// 如果找到这样的元素，删除它（维护最小末尾元素）if (it != dp.end()){dp.erase(it);}// 插入当前元素的位置dp.insert(m[b[i]]);}// 输出最长递增子序列的长度cout << dp.size();return 0;
}
【运行结果】
5
3 2 1 4 5
1 2 3 4 5
3