Algorithms&Data Structures

浅谈求最长不上升子序列的nlogn做法

先来抛个经典题目

Description

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

输入导弹依次飞来的高度(雷达给出的高度数据是\leq 50000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

Sample Input

389 207 155 300 299 170 158 65

Sample Output

6

2

Solution

经典的导弹拦截题目,经典的线性DP,设dp[i]表示以第i位置开头的最长长度,容易得出状态转移方程dp[i]=max(dp[i],dp[j]+1)(i+1\leq j\leq n),需要注意的是,i要从n循环到1,因为状态转移时需要保证i后面的dp值已经预处理好才能进行转移,时间复杂度O(n^2)

先抛个第一问的代码

关于第二问,抛开问题不谈,先来介绍一下离散数学中的几个概念和定理。

①偏序关系:设R是集合A上的一个二元关系,若R满足自反性、反对称性和传递性,则称RA上的偏序关系。

以样例输入为例,集合A=\{ 389,207,155,300,299,170,158,65\},则二元关系R用关系矩阵表示如下所示。

M _R=\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 &1\end{bmatrix}

显然二元关系R满足自反性、反对称性和传递性,是偏序关系。

②可比、不可比:设(A,\preceq )是一个偏序集,对于任意的x,y\in A,若x\preceq yy\preceq x,则称xy可比,否则就称它们不可比。

③链、反链:设(A,\preceq )是一个偏序集,BA的一个子集,如果B中任意两个元素可比,则(B,\preceq )是一条链,如果B中任意两个元素不可比,则(B,\preceq )是一条反链。

Dilworth定理:对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目。

其对偶形式:对于任意有限偏序集,其最长链中元素的数目必等于最小反链划分中反链的数目。

由此可见,题目的第二问就是求最小链划分中链的数目,而第一问我们已经求出最大链中元素的数目,所以由Dilworth定理可得,我们再求出最大反链中元素的数目就是第二问的答案,只需再DP一次即可。

第二问代码

至于Dilworth定理的证明,这里便不再赘述,有时间会写一篇总结(等想起来再说吧233)

下面介绍一下nlogn的做法(划重点!!!)

花里胡哨的方法下面有,这里先说最浅显易懂的

维护一个单调不增的单调栈S,最终我们想要这个栈里存储的元素个数就是第一问的答案,那么我们每遇到一个高度时就和栈顶元素进行比较,这里我们假设该高度为x,栈顶元素为S[top],如果x<=S[top],说明现在的高度能够直接接在栈的后面,那么我们直接S[++len]=xlen为栈内元素个数,如果x>S[top],发扬瞎搞精神,没有条件创造条件也要上,由于栈内元素是有序的,二分查找出栈内第一个小于等于x的元素,把这个元素踹掉换成x

为什么这样做是正确的呢?

我们可以这样想,假设二分查找找到的第一个小于等于x的元素为y,如果y在栈顶,那么直接替换就好了,因为替换后的栈顶元素工作能力比之前的强,后面可能能接上更多的元素,如果y不在栈顶,那么我们可以直接替换掉它,因为y后面不可能再用到了,既然这个位置注定存在,那么我们这里放y还是放x都无所谓。

放一个第一问nlogn的代码,第二问的代码就不需要了,按照上面的定理再用同样方法做就OK了。

Special

多加了个Special模块,专门列一些大犇们的做法,真的是绝了!

法一:线段树/树状数组优化DP

注意到导弹的高度都是不超过50000的正整数,可以以导弹高度为下标建立线段树,为什么不直接以序列下标建线段树呢?我们可以看到,方程转移是有条件的,符合条件才进行转移,如果我们去判断是否能够转移,那么时间复杂度还是O(n^2),并没有起到优化的效果,所以我们只能另辟蹊径,直接以导弹高度建立线段树,这样转移的时候直接查询\leq a[i]的最大值即可,晚上想了好久为什么这样是正确的,万一序列里有比当前高度大且比它靠前的存在呢,结果发现这种担心完全是多余的,我们是从后往前循环,每个循环的点的状态只与序列里比它靠后的有关,虽然比它靠前的比它高度高,但是还没转移到,当然不会对当前转移产生影响。后来我又想了一个问题(我为什么老是自己给自己找麻烦),就是这个线段树到底是建立在什么基础上的,往常我们使用线段树是直接针对想要操作的序列建的,而针对这个问题,线段树很明显是想要操作dp值,但是下标又是导弹高度,后来想明白对于这个序列,它的高度、序列下标和dp值一体的,也就是说,我们想要操作一个dp值的时候,这个dp值必定对应着一个导弹高度和一个序列下标,所以我们这个线段树里面的值虽然是对应区间dp值的最大值,但是我们转移的时候在循环中已经利用该dp值所对应的导弹高度和序列下标作出了是否能够转移的判断,线段树的作用仅仅是转移。

需要注意的是,这里初始的dp值不是1而是0了,为什么会出现这种情况,因为之前我们状态转移的时候是以序列下标为下标进行转移的,所以并不存在重复的情况,而我们以导弹高度为下标的时候,导弹高度可能存在重复的情况,我们将初始值设为0,那么进行转移的时候,假如该点序列后面没有比该点高度小的话,那么在方程dp[i]=max(dp[i],dp[j]+1)中,dp[i]的值应该是不变的,然而dp[i]的值本身就应该是1,所以这里我们直接查询出\leq a[i]再加1就能满足转移方程的所有情况。

第二问就不说了,还是上面那个定理。

法二:最小路径覆盖

此法针对第二问,我们把每个导弹拦截系统能够拦截的导弹按照顺序排在一起,这些导弹构成了一条链,那么我们可以把这条链抽象到图论上,我们假设这些导弹构成了一张图,也就是说每个x\preceq y我们都连一条x->y的边,那么我们就能得到一张DAG(有向无环图),那么第二问所求的就是求DAG中的最小不相交路径覆盖。

首先我们需要拆点,将每个点x拆成出点x1和入点x2,分别对应着出边和入边,然后根据导弹之间的高度关系进行连边,对于每一条边都是x1y2连一条边,这样连边和原先的DAG是等价的,因为点与点之间的连接关系没有改变,只是把一个点拆成了入点和出点,为什么要这样连边呢?因为我们要将有向图变成二分图。

因为我们要求DAG的最小不相交路径覆盖,而最小路径覆盖=点数-最大匹配数,为什么呢?假设我们一开始没有任何连边,那么我们要实现最小覆盖的路径数是点数n,每当我们在二分图中获得一个匹配,相当于在两个点连了一条边,那么路径数就要减1,而我们前面的拆点操作正好能够保证该点作为中介点的可能性,假设该点是中介点,正因为入点和出点正好在图的两边,它们有可能成为最大匹配方案中的两条边,那么正好能够形成一个以该点为中介点的通路,这就是把有向图变成二分图的必要性。

用网络流匈牙利算法均可,匈牙利算法的时间复杂度为O(VE),其中V是二分图中左边点的个数,E是二分图中边的个数。

 

发表评论

邮箱地址不会被公开。 必填项已用*标注