Luogu P1439 【模板】最长公共子序列
【模板】最长公共子序列
题目描述
给出 \(1,2,\ldots,n\) 的两个排列 \(P_1\) 和 \(P_2\) ，求它们的最长公共子序列。
输入格式
第一行是一个数 \(n\)。
接下来两行，每行为 \(n\) 个数，为自然数 \(1,2,\ldots,n\) 的一个排列。
输出格式
一个数，即最长公共子序列的长度。
样例 #1
样例输入 #1
5
3 2 1 4 5
1 2 3 4 5
样例输出 #1
3
提示
- 对于 \(50\%\) 的数据， \(n \le 10^3\)；
- 对于 \(100\%\) 的数据， \(n \le 10^5\)。
题解
$ LCS $ (最长公共子序列)的板子题；
法一
首先介绍特殊方法；
注意到两个序列$ A $ 和 $ B $中任意一个序列都没有重复元素，则：
对于两个序列$ A $ 和 $ B $，如果 $ A $ 是单增的，那么此题就转变成求 $ B $ 的 $ LIS $（最长上升子序列）；
如何将 $ A $ 变为单增序列？很简单，只需重定义 $ < $ 即可，按从 $ A $ 中出现顺序的先后为依据定义 $ < $；
如序列
3 2 1 4 5
依据上述定义，则可知 $ 3 < 2 < 1 < 4 < 5 $，此时我们依据这个大小关系去找 $ B $ 的 $ LIS $ 即可；
其实只需离散化一下即可操作，具体实现不再细说；
注意： 此方法只适用于没有两个序列中各自都没有重复元素的情况，因为如果有重复元素，就很可能出现 $ X > Y \ and \ X < Y $ 的情况，显然不对；
时间复杂度
朴素：$ \Theta(n ^ 2) $；
二分查找优化： $ \Theta(n \ log \ n) $；
那如果有重复元素，该怎么做呢？
法二
讨论通式通法；
继承 $ DP $ 的思想，我们可以先将一个序列 $ A $ 输入，对于序列 $ B $ 的每一个元素，它能为答案做贡献，当且仅当这个元素和 $ A $ 中的某个元素相同时（此时对答案的贡献是 $ + 1 $）；
可以定义 $ f[i] $ 表示 $ A $ 的前 $ i $ 个元素与 $ B $ 的最长 $ LCS $；
遍历 $ B $，倒着寻找所有与 $ B[i] $ 相同的 $ A $ 的元素的位置（设为 $ j $）， 则状态转移方程为：
\[f[i] = \max(f[i], max(f[1] \to f[j - 1]) + 1) \]其中 $ max(f[1] \to f[j - 1]) $ 的意义为找出 $ A $ 的前 $ 1 $ 到前 $ j - 1 $ 个长度的 $ LCS $ 的最大值；
注意：
-
需要倒序，因为如果顺序，则当在一个相同的 $ B[i] $ 进行更新时，如果出现 $ j > i $，那么 $ f[j] $ 可能会被 $ f[i] $ 更新，这就相当于一个 $ B $ 中的数同时对应了两个 $ A $ 中的数，显然不对；
-
找出 $ A $ 中对应的所有 $ B[i] $ 的位置，可以用 $ vector $ 预处理；
-
查询区间最值，可以用线段树维护；
时间复杂度
$ \Theta(n \ log \ n) $；
代码
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n;
vector<int> v[1000005];
int f[1000005];
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
struct sss{
int l, r, ma;
}tr[90000005];
void bt(int id, int l, int r) {
tr[id].l = l;
tr[id].r = r;
if (l == r) {
tr[id].ma = f[l];
return;
}
int mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
void add(int id, int pos, int d) {
if (tr[id].l == tr[id].r) {
tr[id].ma = d;
return;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (pos <= mid) add(ls(id), pos, d);
else add(rs(id), pos, d);
tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
int ask(int id, int l, int r) {
if (l > r) return 0;
if (tr[id].l >= l && tr[id].r <= r) return tr[id].ma;
int mid = (tr[id].l + tr[id].r) >> 1;
if (r <= mid) return ask(ls(id), l, r);
else if (l > mid) return ask(rs(id), l, r);
else return max(ask(ls(id), l, mid), ask(rs(id), mid + 1, r));
}
int main() {
cin >> n;
int x;
for (int i = 1; i <= n; i++) {
cin >> x;
v[x].push_back(i);
}
bt(1, 1, n);
for (int i = 1; i <= n; i++) {
cin >> x;
for (int j = v[x].size() - 1; j >= 0; j--) {
f[v[x][j]] = max(f[v[x][j]], ask(1, 1, v[x][j] - 1) + 1);
add(1, v[x][j], f[v[x][j]]);
}
}
cout << tr[1].ma;
return 0;
}
另一个例题
把 $ n $ 改为 $ 5 * n $ 即可；
代码
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n;
vector<int> v[1000005];
int f[1000005];
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
struct sss{
int l, r, ma;
}tr[90000005];
void bt(int id, int l, int r) {
tr[id].l = l;
tr[id].r = r;
if (l == r) {
tr[id].ma = f[l];
return;
}
int mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
void add(int id, int pos, int d) {
if (tr[id].l == tr[id].r) {
tr[id].ma = d;
return;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (pos <= mid) add(ls(id), pos, d);
else add(rs(id), pos, d);
tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
}
int ask(int id, int l, int r) {
if (l > r) return 0;
if (tr[id].l >= l && tr[id].r <= r) return tr[id].ma;
int mid = (tr[id].l + tr[id].r) >> 1;
if (r <= mid) return ask(ls(id), l, r);
else if (l > mid) return ask(rs(id), l, r);
else return max(ask(ls(id), l, mid), ask(rs(id), mid + 1, r));
}
int main() {
cin >> n;
int x;
for (int i = 1; i <= 5 * n; i++) {
cin >> x;
v[x].push_back(i);
}
bt(1, 1, 5 * n);
for (int i = 1; i <= 5 * n; i++) {
cin >> x;
for (int j = v[x].size() - 1; j >= 0; j--) {
f[v[x][j]] = max(f[v[x][j]], ask(1, 1, v[x][j] - 1) + 1);
add(1, v[x][j], f[v[x][j]]);
}
}
cout << tr[1].ma;
return 0;
}