1. 题目

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

题目描述

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

输入格式

第一行是一个数 $n$。

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

输出格式

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

输入输出样例

输入 #1

5 
3 2 1 4 5
1 2 3 4 5

输出 #1

3

说明/提示

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

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

2. 题解

分析

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

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

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

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

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

代码

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