1. 题目

题目链接：P1439「【模板】最长公共子序列」 。

题目描述

给出 1,2,…,n1,2,\ldots,n 的两个排列 P1P_1 和 P2P_2，求它们的最长公共子序列。

输入格式

第一行是一个数 nn。

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

输出格式

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

输入输出样例

输入 #1

1
2
3
5 
3 2 1 4 5
1 2 3 4 5

输出 #1

1
3

说明/提示

  • 对于 50%50\% 的数据，n≤103n \le 10^3；

  • 对于 100%100\% 的数据，n≤105n \le 10^5。

2. 题解

分析

这是一道 LCS 的模板题，但是如果只用朴素的动态规划来解，复杂度是 O(n2)O(n^2)，结果终究会 TLE。和 LCS 类似的是 LIS，然而 LIS 有 O(nlog⁡n)O(n \log{n}) 的解法，幸运的是部分 LCS 问题可以用 LIS 来解。

  • 在 LCS 中，两个序列中的元素仅表示一种符号，用来判定是否相等的符号，对于符号背后具体的数值对 LCS 的结果并没有影响。

  • 在 LIS 中，是需要考虑序列元素的数值大小关系的。

若 LCS 的两个序列中的其中一个元素互异，则可以用 LIS 来解。在此类 LCS 中，不防假设序列 AA 中元素是互异的，设序列 AA 的长度为 nn，则我们可以考虑将 AA 的元素按照出现顺序依次映射到 1…n1 \ldots n 上，从而得到 AA 中元素与数值的一一对应关系。然后根据 AA 元素的映射表，来计算序列 BB 元素对应的映射值；对于在 BB 中存在而不在 AA 中存在的元素，直接舍弃即可，因为它们必然不会出现在 LCS 中。如此，映射完 BB 得到的数值序列设为 CC，其长度为 mm。则此时只需要计算序列 CC 的 LIS 即可。这是因为序列 AA 映射后的序列是一个递增的数值序列，因此 AA 和 CC 的公共子序列也是递增子序列，最长公共子序列也是最长递增子序列，即序列 CC 的最长递增子序列。

针对这道题而言，由于两个序列都是 1…n1 \ldots n 的排列，因此可以转为 LIS 问题来求解。

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

// 最长递增子序列
struct LIS{
    #ifndef _LIS_
    #define ll int 
    #define MAXN 100005
    #endif 
    ll n;
    ll A[MAXN];
    LIS(): n(0) {}
    // 二分+栈求 LIS 长度
    // 复杂度 O(nlogn)
    ll length() {
        ll cntn = n;
        ll *seqa = A;
        vector <ll> lis;
        lis.push_back(seqa[0]);
        for(ll i = 1; i < cntn; ++i) {
            if(seqa[i] > lis.back()) {
                lis.push_back(seqa[i]);
            } else {
                ll pos = lower_bound(lis.begin(), lis.end(), seqa[i]) - lis.begin();
                lis[pos] = min(lis[pos], seqa[i]);
            }
        }
        return lis.size();
    }
};

int main()
{
    int n;
    int P[MAXN];
    LIS lis;
    scanf("%d", &n);
    lis.n = n;
    for(int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        P[a] = i; 
    }
    for(int i = 0; i < n; ++i) {
        int b;
        scanf("%d", &b);
        lis.A[i] = P[b];
    }
    printf("%d\n", lis.length());
    return 0;
}