题解：P1439 【模板】最长公共子序列

题目大意

给定

1

至

n

的两种排列，求两种排列下的最长公共子序列的长度。

解题思路

本题乍看是最长公共子序列的模板，但是数据范围会超空间和时间。再看题目给定的序列是

1

至

n

的排列，即在序列一中存在的元素必然在序列二中存在。

分析问题发现如果我们对序列一中的第

i

个数

a_i

映射为

i

。这样序列一就是升序序列。考虑对于序列一中每一个数都在序列二中存在，那么只需要找到序列二映射后的元素的最长升序序列即可找到答案。

这样本题的做法转换成了求最长上升子序列，需要效率为

O(n\log{n})

的算法。

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e5+5;
int a[N], b[N], mp[N], dp[N];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		mp[a[i]] = i;
	}
	for (int i = 1; i <= n; i++)
		scanf("%d", &b[i]);
	int len = 1;
	dp[1] = mp[b[1]];
	for (int i = 2; i <= n; i++) {
		if (dp[len] < mp[b[i]]) {
			dp[++len] = mp[b[i]];
		} else {
			int x = lower_bound(dp + 1, dp + 1 + len, mp[b[i]]) - dp;
			dp[x] = mp[b[i]];
		}
	}
	cout << len;
	return 0;
}

题解：P1439 【模板】最长公共子序列

文章操作

题目大意

解题思路

相关推荐

评论

题解：P1439 【模板】最长公共子序列