洛谷-P1439 【模板】最长公共子序列（LCS优化版本）

题目描述

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

输入格式

第一行是一个数 n*n*。

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

输出格式

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

输入输出样例

输入 #1

5 
3 2 1 4 5
1 2 3 4 5

输出 #1

3

说明/提示

• 对于 50\%50% 的数据， n \le 10^3*n*≤103；
• 对于 100\%100% 的数据， n \le 10^5*n*≤105。

---

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> seq(100005), discrete(100005), d(100005);

int solve()
{
    d[1] = discrete[seq[0]];
    int len = 1;
    for (int i = 1; i < n; ++i) {
        int target = discrete[seq[i]];

        int left = 1, right = len + 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (d[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == len + 1) d[++len] = target;
        else d[left] = target;
    }

    return len;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        int num; cin >> num;
        discrete[num] = i + 1;
    }

    for (int i = 0; i < n; ++i) {
        cin >> seq[i];
    }

    cout << solve() << endl;

    return 0;
}

两个序列的元素都是从1到n的n个数，打乱顺序排列，比如例子：

3 2 1 4 5
1 2 3 4 5

现在我们用一种办法映射，将3映射成a，2映射成b，以此类推，则第一个序列变成了：

a b c d e

然后看第二个序列按照这个规则的映射：

c b a d e

两个的公共子序列，无论这个子序列怎么从第一个序列里面选，它都是升序的，所以只需要从第二个序列找LIS即可，于是就可以用二分优化了。