【模板】P1439 最长公共子序列

P1439 【模板】最长公共子序列（洛谷题面）

题目

题目描述：

给出 $1,2,\ldots,n$ 的两个排列 $P_1$ 和 $P_2$ ，求它们的最长公共子序列。

输入格式：

第一行是一个数 $n$。

接下来两行，每行为 $n$ 个数，为自然数 $1,2,\ldots,n$ 的一个排列。

输出格式：

一个数，即最长公共子序列的长度。

数据范围与说明：

• 对于 $50\%$ 的数据， $n \le 10^3$；
• 对于 $100\%$ 的数据， $n \le 10^5$。

输入输出样例 #1

输入：

5 
3 2 1 4 5
1 2 3 4 5

输出：

3

题意

给定 $1 \ldots n$ 的两个排列 $P_1$、$P_2$，求它们的最长公共子序列（LCS）长度。

思路

经典做法是 $O(n^2)$ 动态规划，但对于 $n \le 10^5$ 的数据会超时。利用“两个序列都是排列”的性质，可以将 LCS 转化为 LIS（最长上升子序列）：

1. 建立哈希（或数组）mp[val] 记录值 val 在序列 $P_1$ 中的位置；
2. 遍历 $P_2$，将 $P_2[i]在 $P_1$ 中的位置mp[P2[i]]` 依次写入新数组；
3. 问题就变成了：求该新数组的 LIS 长度，使用 lower_bound + 贪心即可达到 $O(n \log n)$。

复杂度：时间 $O(n \log n)$，空间 $O(n)$。

代码

#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;
}