洛谷【p1439】排列LCS问题 树状数组优化求LIS

缘起

继续学习树状数组优化LIS. 洛谷【p1439】排列LCS问题

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
题目描述
给出1-n的两个排列P1和P2，求它们的最长公共子序列。

输入格式
第一行是一个数n，

接下来两行，每行为n个数，为自然数1-n的一个排列。

输出格式
一个数，即最长公共子序列的长度

输入输出样例
输入 #1复制
5 
3 2 1 4 5
1 2 3 4 5
输出 #1复制
3
说明/提示
【数据规模】

对于50%的数据，n≤1000

对于100%的数据，n≤100000

关于LCS（最长公共子序列）问题, 【2】中是给出过朴素dp解法的. 但是本题的数据规模达到了1e5, 【2】的解法显然只能骗小数据分. 所以需要使用树状数组优化.

本题的想法很直接. 

1
2
3
4
注意到题目中的两个序列都是1~n的一个排列。若其中一个排列是1,2,3…n，那么他们的LCS（最长公共子序列）就是
就是另一个序列的LIS（最长上升子序列）。如果两个序列的排列都不是1,2,3…n，那么我们可以认为其中一个序列是
1,2,3..n，然后把第一个序列的a[1]映射到1，a[2]映射到2，a[n]映射到n，对b序列也按照a序列的映射规则处
理，这样再求b序列的LIS即可。

但是对于一般的LCS（最长公共子序列）问题不能使用这种办法优化到nlogn

代码没怎么写注释, 详细注释参见【1】

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 100005;
int n, a[maxn], b[maxn], c[maxn],p[maxn],dp[maxn],cc[maxn],ans; // cc是dp的树状数组
struct kk
{
	int val,idx;
	bool operator<(kk &o)
	{
		return val<o.val; // bb中没有相同的数
	}
}bb[maxn];

inline int lowbit(int i)
{
	return i&-i;
}

int query(int i)
{
	int ret = 0;
	while(i)
	{
		ret = max(ret, cc[i]);
		i-=lowbit(i);
	}
	return ret;
}

void updata(int i,int x)
{
	while(i<=n)
	{
		cc[i] = max(cc[i], x);
		i+=lowbit(i);
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1;i<=n; i++)
	{
		scanf("%d", a+i);
		c[a[i]] = i; // 映射
	}
	for (int i = 1,x;i<=n; i++)
	{
		scanf("%d", &x);
		bb[i].val = b[i] = c[x];
		bb[i].idx = i;
	} // 利用c将b映射成1,..,n的一个排列, 则答案就是b中的lis（因为b序列中的数两两不同,所以严格、非严格答案一样）
	sort(bb+1,bb+n+1);
	for (int i = 1;i<=n;i++)
	{
		p[bb[i].idx] = i;
	}
	for (int i = 1;i<=n;i++)
	{
		dp[p[i]] = query(p[i]-1)+1;
		ans = max(ans, dp[p[i]]);
		updata(p[i], dp[p[i]]);
	}
	printf("%d", ans);
	return 0;
}

ac情况

1
2
3
4
5
6
所属题目
P1439 【模板】最长公共子序列
评测状态
Accepted
评测分数
100

参考

【1】https://yfsyfs.github.io/2019/10/21/洛谷【p1020】导弹拦截-树状数组优化求LIS/

【2】https://yfsyfs.github.io/2019/07/28/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97%EF%BC%88LCS%EF%BC%89%E9%97%AE%E9%A2%98-hdu-1243-%E5%8F%8D%E6%81%90%E8%AE%AD%E7%BB%83%E8%90%A5/