1. 题目

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

题目描述

给出 1,2,,n1,2,\ldots,n 的两个排列 P1P_1P2P_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\% 的数据,n103n \le 10^3

  • 对于 100%100\% 的数据,n105n \le 10^5

2. 题解

分析

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

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

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

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

针对这道题而言,由于两个序列都是 1n1 \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;
}