【动态规划】LIS与LCS(最长上升子序列)

【动态规划】LIS与LCS(最长上升子序列)


引子-LIS 问题#

这几天在学习DP(动态规划),里面第一个接触到的问题就是LIS问题,这里简单概述如下:

给定一个长度为NN的数列AA,求数值单调递增的子序列的的长度最长是多少?

其中 LIS(最长上升子序列)指的是从序列 A 中选择若干个 i,使得i1<i2<i3...<ini_{1}<i_{2}<i_{3}...<i_{n}的同时满足Ai1<Ai2<Ai3...<AinA_{i_{1}}<A_{i_{2}}<A_{i_{3}}...<A_{i_{n}}


LIS 的朴素解法#

最朴素的想法就是用一个数组DP[i]DP[i]表示在1i1-i范围内的 LIS 长度,初始化DP[i]DP[i]11(它自己一个数作为一个 LIS)。如果在小于1i1-i的范围内有满足 LIS 定义的情况,就可以转移DP[i]DP[i]的值,代表选入这个范围和A[i]A[i]做为 LIS 的一部分。

我们要遍历到DP[i]DP[i]时同时遍历所有在1i1-i内的状态,显然每次转移都是O(N)O(N)的时间复杂度,总复杂度为O(N2)O(N^2),状态转移方程如下:

DP[i]=max(DP[i],DP[j]+1)(j<i)DP[i] = max(DP[i], DP[j] + 1) | (j < i)

显然O(N2)O(N^2)的时间复杂度是无法满足 OIer 的,因此我们要进行优化。


LIS 的贪心二分优化#

优化思路#

为什么朴素算法慢呢?因为我们把所有情况枚举了一遍,而最后留下的只有一种。LIS 的朴素算法在那些本不需要枚举的状态上浪费了时间,自然就不行了。

我们知道,LIS 是一个严格单增的数列,那么在两个 LIS 长度相同的情况下,我们希望它能扩展到的长度尽可能长,自然是希望LIS 结尾元素尽可能小。那么思路就有了,我们使用一个数组G[i]G[i]保存长度为ii的 LIS 的结尾元素值记录当前最长的 LIS 长度为tottot,对于每一个A[i]A[i],如果A[i]>G[tot]A[i] > G[tot],说明当前可以把A[i]A[i]接到这一条所谓最长的 LIS 后面,则G[++tot]=A[i]G[++tot] = A[i]

那么我们的问题就是如何维护GG数组。其实很简单,思路就是我们上面的思路,但是有一个问题,如果A[i]G[tot]A[i] \leq G[tot],应该怎么办呢?

那么根据我们的优化思路,我们要尽可能确保当前GG数组里面存储的是当前长度为ii的 LIS 序列的最优解,也就是 结尾元素尽可能小的情况。所以我们要在GG数组中找到第一个大于A[i]A[i]的元素G[j]G[j],用A[i]A[i]更新G[i]G[i]

可是如果单纯遍历,复杂度又双叒叕回到了O(N2)O(N^2)级别,所以……

二分优化#

显然,GG数组是一个单调递增的数组,自然地可以使用二分查找优化时间复杂度。把时间复杂度降到O(NlogN)O(N\,log\,N)级别。

代码整合#

那么到目前为止,我们亲爱的DPDP数组就寿终正寝了,换成了我们新的GG数组~~(什么NTR剧情)~~。

下面是代码示例,基础 LIS:

CPP
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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX 100005
#define INF 1e9

using namespace std;

int A[MAX]; //存数字
int G[MAX]; //我们亲爱的G数组
int tot = 1;

int main()
{
    int N = 0; //长度
    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &A[i]);
        G[i] == INF; //初始化为1e9
    }

    G[1] = A[1]; //我们开始的起点

    for(int i = 2; i <= N; i++)
    {
        if(A[i] > G[tot]) //只要能插入,就先插入
            G[++tot] = A[i]; //初始化最后一个元素值
        else
        {
            int l = 1, r = tot, mid; //新建变量
            while (l < r)
            {
                //基础二分查找
                mid = (l + r) >> 1;
                if(G[mid] > A[i]) r = mid;
                else l = mid + 1;
            }
            G[l] = min(G[l], A[i]); //赋值,加MIN保险
        }
    }

    printf("%d", tot); //输出答案

    return 0;
}

LIS 例题#

这里给出一道 LIS 模板题:导弹拦截LIS 经典。

将拦截的导弹的高度提出来成为原高度序列的一个子序列,根据题意这个子序列中的元素是单调不增的(即后一项总是不大于前一项),我们称为单调不升子序列。本问所求能拦截到的最多的导弹,即求最长的单调不升子序列。(其实只要判断改一下就好啦!)

第一问#

没什么好说的,跑一次示例代码完事。

注意这里GG数组递减!请修改二分查找!

第二问#

那么既然是单调不升子序列,我们考虑朴素算法,那么GG数组就要求存储最大的值,每次执行完一次计算,就把选中的元素移除。重复计算,直到全部移除,记录计算次数,输出为答案。

但是这样显然太笨了!我们要优化优化优化!

我们不妨改变一下GG数组的含义,用G[i]G[i]存第ii个系统当前能够拦截的高度,同时我们把这些系统按从小到大排列——类似于原来的GG数组。显然每次遍历到导弹A[i]A[i]时,我们拿最小的G[i]A[i]G[i] \geq A[i]是最优解。然后更新G[i]G[i]的值,显然更新之后排列还是从小到大,GG数组仍然是单调递增的,因此不需要重新排序。当然如果没有满足G[i]A[i]G[i] \geq A[i]的情况,就新增一个系统。

只要我们仍然保存时间复杂度在O(NlogN)O(N\,log\,N) 级别,可以通过10510^5的数据。

代码整合#

下面是 AC 代码:

CPP
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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAX 100005
#define INF 1e9

using namespace std;

int A[MAX]; //存数字
int G[MAX];	//我们亲爱的G数组
int tot = 1;

int main()
{
	int N = 0; //长度
	while(~scanf("%d",&A[++N])); --N;

	G[1] = A[1]; //我们开始的起点

	for(int i = 2; i <= N; i++)
	{
		if(A[i] <= G[tot]) //只要能插入,就先插入
			G[++tot] = A[i]; //初始化最后一个元素值
		else
		{
	        int l = 1, r = tot, mid;
	        while (l < r)//获得下标,注意这里G数组递减
	        {
	        	//基础二分查找
	        	mid = (l + r) >> 1;
	        	if(G[mid] >= A[i]) l = mid + 1;
	        	else r = mid;
	        }
			G[l] = max(G[l], A[i]); //赋值,加MAX保险
		}
	}

	printf("%d\n", tot); //输出答案一

	//重置数据
	tot = 1;
	memset(G, INF, sizeof(G));
	G[1] = A[1];

	for(int i = 2; i <= N; i++)
	{
	    int l = 1, r = tot, mid;
	    while (l < r)//获得下标,当然也可能没有
	    {
	    	//基础二分查找
	    	mid = (l + r) >> 1;
	    	if(G[mid] >= A[i]) r = mid;
	    	else l = mid + 1;
	    }
		if(G[l] >= A[i]) G[l] = A[i]; //如果找得到,赋值
		else G[++tot] = A[i]; //如果找不到,初始化一个新的系统
	}

	printf("%d\n", tot); //输出答案二

	return 0;
}