LIS LCS 以及相应DP模型的拓展 (一)

本来只是想写一篇题解，但总喜欢扯得太远，那干脆定一个大点的题把这些都包括进来吧。可能废话比较多，但有时间还是看看吧，说不定能有什么新思考
本文主要讲讲最长递增子序列（LIS），最长公共子序列（LCS）以及一些拓展dp问题。当然这些问题有的不止有dp解法。

最长递增子序列

给定一个数列 $a_i$，求他们的最长严格递增子序列。

可见HDOJ-1257

LIS的求法

当让我们也可以不求严格递增只求递增，递减也行，主要思想是一样的。
这里再给出两个概念

子序列：把一个序列 $a_i$ 删除某些元素得到的序列 $b_j$,称 $b_j$ 为 $a_i$ 的子序列

注意把子序列和子串的概念区分开，子串是连续的，子序列可以不连续。但他们的相对位置都没有发生变化，序列 $a_i$ 中 $m$ 在 $n$ 的后面，子序列和子串中还是 $m$ 在 $n$ 的后面。

严格递增序列：一个序列 $a_n$，对于任意的 $1 \leq i < j \leq n$，都有 $a_i < a_j$

通俗的讲就是一个序列，后面的数都要比前面的数大，注意严格是 $<$ 不是 $\leq$的意思，$\leq$ 叫做递增，不叫严格递增。

朴素

那这问题怎么做捏。
首先思考朴素做法，对于数列中的每一个数，暴力搜索以她为结尾（为开头也可以）的严格递增子序列长度，取最大值。时间复杂度为 $O(2^n)$ 蛮难绷住的。上个代码（注意这里展示的代码都是针对LIS，不是针对HDOJ-1257的）

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 <iostream>
#include <algorithm>

using namespace std;
//a数组存序列,ans存答案
int n,a[1314520],ans;
//计算以a[i]结尾的上升子序列的长度，并更新答案
void dfs(int i,int len);

int main(){
	//读入数组
	cin >> n;
	for (int i = 1;i <= n;++i) cin >> a[i];
	//枚举子序列的结尾a[i]	
	for (int i = 1;i <= n;++i) dfs(i,1);
	//输出答案
	cout << ans << endl;
	return 0;
}
 
void dfs(int i,int len){
	//枚举每条路
	for (int j = 1;j < i;++j)
		//如果这条路合法，就搜她
		if (a[j] < a[i]) dfs(j,len+1);
	
	//更新答案
	ans = max(ans,len);
}

这是很慢的代码，随机数据测试发现，序列长度132个的就得跑6秒。当然是行不通的（TLE）

DP

思考改进，我们可以发现dfs效率慢的原因就是重复搜索了很多状态，理论上我们可以用记忆化搜索来优化，记忆化搜索其实已经就是动态规划了。（以后有空我再展开说说这一块）但这个dfs不是单纯的返回某个值，而是不断更新全局最大值，所以不好实现记忆化搜索，我们直接尝试dp。

能用dp三个必备要素：最优子结构，无后效性，子问题重叠

_Future never has to do with past time ,but present does_.

然而我们使用dp时还是凭经验行事比较多，甚至上面一些“必备要素”不满足的情况下我们还有处理方法（挖坑）。

我们考虑dp状态的时候一般有两条路可以走，一是从阶段，状态，决策去考虑，这种类似于递推思想，二是从集合的角度思考问题，一个状态看成一个集合，考虑他包含了什么子集，这种就类似于递归的思想。不过这只是思考方式，dp的代码实现其实都是可以递归和递推相互转化的。本质也可以从图论的角度思考（多扯一些）。

动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序

上面的东西有点深了，初学不理解没有关系，可以以后慢慢回味

我们尝试从集合的角度思考问题（我觉得这样比较直观）。

  1. 首先考虑状态表示，这一步还是比较吃经验的（多刷题），在这种序列dp里面，我们状态表示都离不开序列的下标。再结合上面暴力搜素的代码，这题我们直接用 $f_i$ 表示以 $a_i$ 结尾的最长递增子序列的长度。
  2. 再思考状态计算，观察这个状态包含了什么子状态，即这个状态能有什么其他状态推过来。可以发现至少这个状态不会和 $i$ 之后的状态有关（也是无后效性），从集合划分考虑状态计算，$f_i$ 包含了不选上 $a_i$ 和选上 $a_i$ 两种子状态，不选上 $a_i$ 的状态就是 $i$ 之前的最长上升子序列的长度，表示出来就是 $\max\limits_{1 \leq j < i} f_j$，而选上的状态就是再加个一，即 $\max\limits_{1 \leq j < i} f_j + 1$。但还要注意的一点是，不是什么时候都可以选上的，要满足递增必须要满足 $a_j < a_i$。两个状态取max，即最后我们推理出来的状态转移方程为把 $f_i$ 全都初始化 $1$ （即以当前 $a_i$ 结尾的数的LIS长度至少为 $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
    #include <iostream>
    #include <algorithm>

    using namespace std;

    const int N = 1314520;
    int a[N],f[N],n,ans;

    int main(){
    	cin >> n;
    	for (int i = 1;i <= n;++i) cin >> a[i],f[i] = 1;

    	//递推，开始dp
    	for (int i = 1;i <= n;++i)
    		for (int j = 1;j < i;++j)
    			//如果a[j]能选，更新答案
    			if (a[j] < a[i])
    				f[i] = max(f[i],f[j]+1);

    	//注意最后答案不一定是以a[n]结尾，所以要遍历一遍取最大值
    	for (int i = 1;i <= n;++i) ans = max(ans,f[i]);
    	cout << ans << endl;
    	return 0;
    }
    时间复杂度为 $O(n^2)$ 已经比暴力快了很多了。不够我们还有更快的 $O(nlogn)$ 的方法

贪心

此做法基于贪心，大致做法就是维护一个数组，并从前往后扫描数组。先讲讲这题最少拦截系统的题解可能更容易理解。

HDOJ-1257题解

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.

(8 是导弹总个数).

input: 8 389 207 155 300 299 170 158 65

输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

output: 2

怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

简要意思就是导弹只能往下打或保持高度不变，所以求的就是至少要多少个不上升子序列能覆盖整个序列。其实球的就是原序列的LIS长度，证明来：

我们如果求出了这些覆盖原序列的最长上升子序列，如样例里的{389,207,155}和{300,299,170,158,65}。那我们肯定能在后一个序列中找到一个数，和前一个数构成上升子序列，否则后一个序列应该接在前一个的后面。得证

也不复杂，所以这题就是求LIS的裸题，可以用上面讲的方法求LIS。但从这题我们可以发现LIS的个数求的就是至少要多少个不上升子序列能覆盖整个序列。所以很自然想到贪心做法。维护一个数组 $d_n$ ，并从前往后扫描数组 $a_n$ 。如果当前数 $a_i$ 比数组 $d_n$ 末尾的数还要大，就把她作为数组末尾元素，数组长度加一。否则就在数组 $d_n$ 中查找第一个大于她的数 $d_k$ ，把 $d_k$ 换成 $a_i$ （即把这个导弹用目前最低位置的拦截系统拦截掉）。我们还可以用贪心的决策包容性去解释这种做法。最后数组长度就是原序列LIS的长度。容易发现数组始终是单调递增的，所以可以用二分优化。总的复杂度为 $O(nlogn)$的。上代码：(注意代码针对的是LIS，不是题目)

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
#include <iostream>
#include <algorithm>
//用一个MAXN宏更方便
#define MAXN 1000010

using namespace std;
//定义变量
int n,a[MAXN],d[MAXN],len,x;
int main(){
    cin >> n;
    for (int i = 1;i <= n;++i) cin >> a[i];
	
	//len初始为1，这里我们下标从1开始
	len = 1;
    d[len] = a[1];
    for (int i = 1;i <= n;++i){
        if (a[i] > d[len])
            d[++len] = a[i];
        else{
			//查找d里第一个不小于a[i]的数，将他替换
			//即把导弹接它后面
            x = lower_bound(d + 1,d+len + 1,a[i]) - d;
            d[x] = a[i];
        }
    }
    cout << len << endl;
    return 0;
}

这就是我们基于贪心的 $O(nlogn)$ 做法。我们从题目出发想到了这种做法，属于是ACMer促进CS发展（）。

说回DP，我们可以基于LIS的dp思想：用 $f_i$ 表示当前状态，可以由 $i$ 前面的状态得到。我们来试试其他类型的问题

最大上升子序列和

给定一个数列 $a_i$，求他们的最大的严格递增子序列的和

注意最大的上升子序列和不一定是LIS的和

还是和LIS一样，我们用 $f_i$ 表示以 $a_i$ 结尾的最大上升子序列和。那状态计算呢，很简单，这里直接给出，可以思考一下:

即

所以只要把上面dp的代码改一个数字，问题就解决了，这里就不上代码了。

登山

五一到了，PKU-ACM队组织大家去登山观光，队员们发现山上一个有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？
详见 noiOJ-1996

当然我们可以用这种方法求最长上升子序列，当然也可以最长下降子序列（LDS）。我们可以改个符号判断，也可反着求一遍LIS。

而这题，我们就可以枚举每个点，求以这个点以这个点开始下山，即以这个点为顶点，能浏览的景点数，取个max即可。求景点数就只要求以这个点为结尾的LIS长度和以这个点为开头的最长下降子序列长度就行。如上所说，正反求两边LIS即可，上个代码

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 <iostream>
#include <algorithm>

using namespace std;

const int N = 1024;
//f[i]存以a[i]结尾的LIS长度
//g[i]存以a[i]开头的LDS长度，
// 即倒过来的a[i]结尾的LIS长度
int f[N],g[N],a[N],n,ans;

int main(){
	//读入数列
    cin >> n;
    for (int i = 1;i <= n;++i) cin >> a[i],f[i] = 1,g[i] = 1;;
    
	//正着来一遍dp求LIS，求f[i]
    for (int i = 1;i <= n;++i) for (int j = 1;j < i;++j)
        if (a[j] < a[i]) f[i] = max(f[i],f[j]+1);
    //反着再来一把遍，求出g[i]
	for (int i = n;i >= 1;--i) for (int j = n;j > i;--j)
        if (a[j] < a[i]) g[i] = max(g[i],g[j]+1);
    
	//最后枚举顶点，能浏览的景点数就为f[i]和g[i]的和
	//因为这么加起来还多加了个自己，所以减去1
    for (int i = 1;i <= n;++i) ans = max(ans,g[i]+f[i]-1);
    cout << ans;
    return 0;
}

好了，这就是LIS的dp了，就讲到这里吧，我们接下来讲讲最长公共子序列LCS

来不及写了，先这样吧，下周回来再讲