题解：洛谷 P1439 两个排列的最长公共子序列

【题目来源】

洛谷：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