2334: 【提高】最长公共子序列(LCS)(2)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
给出 的两个排列 和 ，求它们的最长公共子序列。
和最长公共子序列(LCS)(1)问题不同的是，本题的 在 之间。
输入
第一行是一个数 ；（ 是 之间的整数）
接下来两行，每行为 个数，为自然数 的一个排列（ 的排列每行的数据都是 之间的数，但顺序可能不同，比如 的排列可以是： ，也可以是 ）。
输出
一个整数，即最长公共子序列的长度。
样例输入 复制
5
3 2 1 4 5
1 2 3 4 5样例输出 复制
3提示
数据范围
对于 的数据，；
对于 的数据，。
#include<bits/stdc++.h>
using namespace std;
const int N = 100100;
int a[N], b[N], c[N], dp[N];
int n, i;
int main() {
cin >> n;
for (i = 1; i <= n; i++) {
scanf("%d", & a[i]);
c[a[i]] = i; //求出a数组的每个数的位置
}
for (i = 1; i <= n; i++) scanf("%d", & b[i]);
//求b数组的每个数在a数组的位置(c[b[i]])的 LIS
dp[1] = c[b[1]];
//边界
int len = 1;
int l, r, mid; //从第2个数开始讨论
for (i = 2; i <= n; i++) { //增加 LIS的长度
if (c[b[i]] > dp[len]) {
len++;
dp[len] = c[b[i]];
} else {
l = 1;
r = len;
while (l <= r) {
mid = (l + r) / 2;
if (c[b[i]] <= dp[mid]) r = mid - 1;
else l = mid + 1;
}
dp[l] = c[b[i]];
}
}
cout << len;
return 0;
}