poj 2533 Longest Ordered Subsequence LIS dp 最长上升子序列

缘起

LIS（longest increment subsequence 最长上升子序列）是经典的dp问题. 遂找题目提交. poj 2533 Longest Ordered Subsequence

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
一个序列我们称之为上升的如果它是严格单调递增的. 那么你现在的任务就是对于给定的一个序列求他的最长上升子序
列的长度.

【输入】
第一行是序列的长度N(1<=N<=1000)
第2行是N个数字, 数字的范围是[0,10000]

【输出】
最长上升子序列的长度

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

【样例输出】
4

【限制】
Time limit 2000 ms
Memory limit 65536 kB

令dp[i]为以a[i]（i>=0）结尾的最长上升子序列的长度. 则
$$
dp[i] = 1+max_{0\le k<i}{dp[k]\ | \ a[k]<a[i] }, \ \ for \ 0<i<n
$$
显然一开始所有的dp[i]为1（初始值必须要为1, 不能为0, 原因很简单,如果初始值dp[i]为0的话， 如果a[i]比任何前面的a[k](k<i)都小的话, 那岂不是dp[i]就是0 了? ）注意，和【1】中可以O(n)不同, 因为【1】中是连续片段，而这里是离散的.

上面的dp的复杂度是O(N^2)的，N的规模只有1000, 所以完全可以接受.

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

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

int n, dp[1005],a[1005];

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 0; i<n;i++)
	{
		scanf("%d", a+i);
	}
	fill(dp, dp+n, 1);// 注意,初始值为1, 不是0, WA了一发~ 
	int ans = 1;
	for (int i = 1; i<n;i++)
	{
		for (int k = 0; k<i; k++)
		{
			if (a[k]<a[i] && dp[i] < dp[k]+1)
			{
				dp[i] = dp[k]+1;
			}
		}
		if (ans < dp[i])
		{
			ans = dp[i];
		}
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Memory 96kB
Length 557
Lang C++
Submitted 2019-08-19 22:41:09
Shared
RemoteRunId 20770556

但是O(n^2)多少让我们不舒服~ 难道没有更快的算法了么?

我们说过——dp的效率很受dp的对象锁影响. 换言之——如果我们改变dp的对象的话, 则可能可以提高dp的效率.

令

1
2
dp[i]=长度为i的LIS中末尾元素的最小值(不存在长度为i的LIS的话，dp[i]就等于INF)，这其实就是一种贪心, 
因为保持长度为i但是末尾元素最小, 这样的LIS才是在所有长度为i的LIS中最有潜力的

注意，我们考虑从前往后逐步插入数字的过程. 伊始 dp[i]皆为 inf. 所以每次插入的过程，例如插入a[j], 则都是插入数列的末尾元素. 我们还是举个例子吧~ 这样理解的更快一些

考虑序列为【7 2 1 5 6 4 3 8 9 】

首先插入7, 则没什么好说的

1
【7】	dp[1]

插入2 ，则因为7>2, 所以替换为2更有潜力

1
【2】	dp[1]

插入1, 则1<2, 所以替换为1更有潜力

1
【1】	dp[1]

插入5， 则

1
2
【1】	dp[1]
【1,5】	dp[2]

插入6 ， 则

1
2
3
【1】	dp[1]
【1,5】	dp[2]
【1,5,6】	dp[3]

插入4， 则

1
2
3
【1】	dp[1]
【1,4】	dp[2]
【1,5,6】	dp[3]

注意，tricky的地方来了——同样是4<5也4<6, 为什么只更新了dp[2]而没有更新 dp[3]? 原因很简单，因为5是最早的一个严格大于4的数字（因为根据dp的定义, dp是严格单增的序列, 所以可以二分，这就是O(nlogn)算法的来由）, 也就是 dp[1]=1<4, dp[2]=5>4, dp[3]=6>4, 所以改变dp[2] 而不是改变dp[3]. 而且如上所示, 你不能改变dp[3]——因为dp[2]=5意味着dp[3]表示的LIS中也一定有5，5>4, 改变了的话, dp[3]就不是LIS了.

插入3， 则

1
2
3
【1】	dp[1]
【1,3】 dp[2]
【1,5,6】 dp[3]

插入8， 则

1
2
3
4
【1】	dp[1]
【1,3】 dp[2]
【1,5,6】 dp[3]
【1,5,6,8】 dp[4]

插入9, 则

1
2
3
4
5
【1】	dp[1]
【1,3】 dp[2]
【1,5,6】 dp[3]
【1,5,6,8】 dp[4]
【1,5,6,8,9】 dp[5]

根据上述例子不难写下如下算法

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

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

int n, dp[1005],a[1005];

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);
	}
	memset(dp, 0x3f,sizeof(dp));
	for (int i = 1; i<=n; i++)
	{
		*lower_bound(dp+1, dp+n+1, a[i]) = a[i]; // 二分搜索
	}
	printf("%d\n", lower_bound(dp+1,dp+n+1, 0x3f3f3f3f)-(dp+1));
	return 0;
}

ac情况

6503338 yfs 1299 Accepted 0 ms 164 KiB g++ 553 B 2019-08-20 08:20:42

参考

【1】https://yfsyfs.github.io/2019/07/20/%E7%BB%8F%E5%85%B8dpdp-%E6%B1%82%E6%9C%80%E5%A4%A7%E7%89%87%E6%AE%B5%E5%92%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97/