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

kuaiCreator · 2025-03-12 11:17:23 · 题解

题目大意

给定 1 至 n 的两种排列，求两种排列下的最长公共子序列的长度。

解题思路

本题乍看是最长公共子序列的模板，但是数据范围会超空间和时间。再看题目给定的序列是 1 至 n 的排列，即在序列一中存在的元素必然在序列二中存在。

分析问题发现如果我们对序列一中的第 i 个数 a_i 映射为 i。这样序列一就是升序序列。考虑对于序列一中每一个数都在序列二中存在，那么只需要找到序列二映射后的元素的最长升序序列即可找到答案。

这样本题的做法转换成了求最长上升子序列，需要效率为 O(n\log{n}) 的算法。

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e5+5;
int a[N], b[N], mp[N], dp[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        mp[a[i]] = i;
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    int len = 1;
    dp[1] = mp[b[1]];
    for (int i = 2; i <= n; i++) {
        if (dp[len] < mp[b[i]]) {
            dp[++len] = mp[b[i]];
        } else {
            int x = lower_bound(dp + 1, dp + 1 + len, mp[b[i]]) - dp;
            dp[x] = mp[b[i]];
        }
    }
    cout << len;
    return 0;
}