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

题意

给定 的两个排列 、，求它们的最长公共子序列（LCS）长度。

思路

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
}