最长升

青葱

2019-04-13 17:42:39

Solution

# 关于LIS的几种解法 ## **一、LIS的朴素做法O($n^2$)** ------------ **f[ i ]:以第i个数为结尾的最长升长度** **w[ i ]:第i个数的权值** ------------ 考虑新加入一个数 j 在原序列后,所有权值小于w[ j ]的数所形成的最长升都能扩展一个位置 换句话说,j 的最长升是从**以比它小且在它左边的数为末尾的最长升**加一个数 j 得到的 ------------ ### **动态转移方程如下:** ### ***f[ j ]=max{ $\sum_{i=1}^j$ f[ i ] | w[ i ] > w[ j ] }+1*** ------------ ```cpp for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ if(w[j]<=w[i]) f[i]=max(f[i],f[j]+1); } } ``` ### **其特点在于:** #### 1. 简单又暴力的美学 #### 2. 可以求出以每个数为结尾的最长升长度 #### 3. 可以顺手求出最长升原序列 ------------ ## **二、LIS单调栈做法O($nlog^{}_{2}n$)** ------------ 假设这里有一个序列是递增的,我们显然可以很好地求出最长升的长度 而对于非递增的序列,我们也可以通过**维护一个单调栈**来使其递增 ------------ ### **单调栈一般流程:** #### 1. 二分找到栈中小于它的第一个数 #### 2. 如果存在,替换它,否则压新数入栈 #### 3. 当前数所在栈中的编号即为以它为结尾的最长升长度 ------------ ### **单调栈设计思路的由来:** ------------ #### 从第一个数到第 n 个数依次插入序列,分析题目的单调性: 设当前要插入第 j 个数,其权为w[ j ] ------------ 1、我们可以轻易的知道,在以第一个数到第 j -1个数为末尾的最长升在位置上是允许被扩展的,第 j 个数可以插入到以它之前所有权值小于w[ j ]的数所形成的最长升后 即:**只要是权值小于等于w[ j ]的数,我们都一视同仁为可扩展数,以其为结尾的最长升,一视同仁为可扩展序列** ------------ 2、我们还可以发现,对于一个数的插入是没有后效性的 即:确定了以w[ j ]为结尾的最长升,**无论在它后面插入多少个数,以w[ j ]为结尾的最长升是不变的** ------------ 3、于是,我们很自然地想,要确定最长升,就要有最长的可扩展序列 即:如果我们能够知道在第1个数到第 j -1个数所形成的不同长度的最长升中, **长度最长且结尾数字小于等于w[ j ]的最长升**,即找到了最优扩展位置,就可以求出以第 j 个数为结尾的最长升 4、更秒的是,我们可以证明,更长的上升子序列的结尾数字一定不小于更短的上升子序列(我们可以通过舍弃长的上升子序列的前几个数得到短的上升子序列) 即:**我们维护的这个栈是单调的**,我们可以二分找到最佳扩展位置 ------------ ### 需要注意的是: 单调栈内在不同位置上的数 即: #### **在第 j 个数之前不同长度上升子序列的最小结尾数字** 而实际上,**我们维护的单调栈并非维护的一个序列,而是不同长度下结尾数字最小的多个序列** 但是,我们在维护单调栈的同时,改变了位置关系,所以,对于单调栈内维护的序列,只有长度与最小末尾数字是可以确定的 ------------ ```cpp for(int i=1;i<=n;i++){ if(b[i]>m[top]) m[++top]=b[i]; else m[lower_bound(m+1,m+top+1,b[i])-m]=b[i]; } ``` ------------ ### **其特点在于:** #### 1. 简洁而又睿智的美学 #### 2. 可以求出以每个数为结尾的最长升长度 #### 3. 不能很有效的求出最长升序列 ------------ ## **三、LIS的DP优化O($nlog^{}_{2}n$)** 基于朴素DP和单调栈的思想: 我们插入到一个数时,仅仅需要知道以比它小的数结尾的最长上升子序列长度 那么我们可以用数据结构维护这个性质 即:**我们需要一种数据结构维护区间最大值和单点插入** 比如:树状数组、线段树 ------------ ### **一般流程:** 我们以w[ j ]作为下标,以第 j 个数能形成的最长升长度为权值 当插入到第 j +1个数时,只需要询问1~w[ j +1]之间的长度最大值 之后插入第 j +1个数,继续下面的数 ------------ ``` for(int i=1;i<=n;i++){ int p=_map[read()]; f[i]=query(p)+1; ans=max(ans,f[i]); add(p,f[i]); } ``` 答案即为以各个数为结尾的最长升中的最大值 ------------ ### 需要注意的是: 1、如果我们用:pair<int.int>(第一维维护最大值,第二维维护对应的位置下标),代替最大值的int,**就能够层层向上,找到原序列** 2、因为下标为权值,所以**对于一般题目需要离散化** ------------ ### **其特点在于:** #### 1. 精简而又巧妙的美学 #### 2. 可以求出以每个数为结尾的最长升长度 #### 3. 可以很有效的求出最长升序列