poj 1631 Bridging signals LIS

缘起

日常水题 poj 1631 Bridging signals

分析

题目比较难读（原谅我的poor English~）

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
给你一个序列，求LIS的长度.

【输入】
第一行是样例数, 后面每个样例的第一行是序列的长度n（1<=<4w）, 然后后面是n个数

【输出】
对每个样例，输出LIS的长度

【样例输入】
4
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
8
8
7
6
5
4
3
2
1
9
5
8
9
2
3
1
7
4
6

【样例输出】
3
9
1
4

【限制】
1s

其实【1】研究过了, 本题尝试打熟.

因为n达到了4w，所以使用朴素的O(n^2)的LIS是会被T的. 所以必须要使用O(nlong)优化——即改变dp的对象为

1
2
3
dp[i]是长度为i的IS的末尾元素的值中最小的(dp[i]伊始全部是inf), 则插入新的数k的时候, 找到>=k的最小
dp[i],改变dp[i]的值, 则最后dp[i]<inf的最大i就是LIS的长度. 则按照此过程更新的dp是严格单增的.
使用二分查找优化. 复杂度为O(nlogn)

ac代码如下

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
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n, dp[40005], inf = 0x3f3f3f3f;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		memset(dp+1, 0x3f, sizeof(int)*n);
		int nn = n,x;
		while(nn--)
		{
			scanf("%d", &x);
			*lower_bound(dp+1, dp+n+1, x) = x;
		}
		printf("%d\n", lower_bound(dp+1, dp+n+1, inf)-(dp+1));
	}
	return 0;
}

ac情况

Status Accepted
Time 110ms
Memory 236kB
Length 541
Lang C++
Submitted 2019-08-28 10:25:12
Shared
RemoteRunId 20810530

参考

【1】https://yfsyfs.github.io/2019/08/19/poj-2533-Longest-Ordered-Subsequence-LIS-dp-%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97/