N种方法妙讲LIS算法

2024-07-28 作者:

N种⽅法妙讲LIS算法

LIS算法经典汇总

假设存在⼀个序列d[1..9] = 2 1 5 3 6 4 8 9 7，可以看出来它的LIS长度为5。下⾯⼀步⼀步试着找出它。

我们定义⼀个序列B，然后令 i = 1 to 9 逐个考察这个序列。此外，我们⽤⼀个变量Len来记录现在最长算到多少了

⾸先，把d[1]有序地放到B⾥，令B[1] = 2，就是说当只有1⼀个数字2的时候，长度为1的LIS的最⼩末尾是2。这时Len=1然后，把d[2]有序地放到B⾥，令B[1] = 1，就是说长度为1的LIS的最⼩末尾是1，d[1]=2已经没⽤了，很容易理解吧。这时Len=1

接着，d[3] = 5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是说长度为2的LIS的最⼩末尾是5，很容易理解吧。这时候B[1..2] = 1, 5，Len＝2再来，d[4] = 3，它正好加在1,5之间，放在1的位置显然不合适，因为1⼩于3，长度为1的LIS最⼩末尾应该是1，这样很容易推知，长度为2的LIS最⼩末尾是3，于是可以把5淘汰掉，这时候B[1..2] = 1, 3，Len = 2

继续，d[5] = 6，它在3后⾯，因为B[2] = 3, ⽽6在3后⾯，于是很容易可以推知B[3] = 6, 这时B[1..3] = 1, 3, 6，还是很容易理解吧？ Len = 3 了噢。

第6个, d[6] = 4，你看它在3和6之间，于是我们就可以把6替换掉，得到B[3] = 4。B[1..3] = 1, 3, 4， Len继续等于3第7个, d[7] = 8，它很⼤，⽐4⼤，嗯。于是B[4] = 8。Len变成4了第8个, d[8] = 9，得到B[5] = 9，嗯。Len继续增⼤，到5了。

最后⼀个, d[9] = 7，它在B[3] = 4和B[4] = 8之间，所以我们知道，最新的B[4] =7，B[1..5] = 1, 3, 4, 7, 9，Len = 5。于是我们知道了LIS的长度为5。

!!!!! 注意。这个1,3,4,7,9不是LIS，它只是存储的对应长度LIS的最⼩末尾。有了这个末尾，我们就可以⼀个⼀个地插⼊数据。虽然最后⼀个d[9] = 7更新进去对于这组数据没有什么意义，但是如果后⾯再出现两个数字 8 和 9，那么就可以把8更新到d[5], 9更新到d[6]，得出LIS的长度为6。

然后应该发现⼀件事情了：在B中插⼊数据是有序的，⽽且是进⾏替换⽽不需要挪动——也就是说，我们可以使⽤⼆分查找，将每⼀个数字的插⼊时间优化到O(logN)~~~~~于是算法的时间复杂度就降低到了O(NlogN)～！借助例题

Problem Description

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

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

Input

输⼊若⼲组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的⾼度(雷达给出的⾼度数据是不⼤于30000的正整数,⽤空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output2

经典LIS算法，与求最⼤上升⼦序列相似：

以数组 h[] 记录拦截系统当前的拦截⾼度，先初始化为最⼤值 INF = 30000+10,

表⽰每⼀个新拦截系统都能拦截所有的导弹，然后遇到⼀个导弹就往前找看是否有已经使⽤了的系统能拦截，如果有，直接⽤；否则重新弄⼀个系统。最后再看⽤了⼏个

第⼀个导弹 389 < h[1] ( h[1] = INF)被第⼀个系统拦截 h[1] = 389第⼆个导弹 207 < h[1] 被第⼀个系统拦截 h[1] = 207第三个导弹 155 < h[1] h[1] = 155

第四个导弹 300 > h[1] , 300 < h[2] ( h[2] = INF ) 所以新开发⼀个系统拦截第四个导弹, h[2] = 300第五个导弹 299 > h[1] , 299 < h[2] 被第⼆个系统拦截 h[2] = 299第六个导弹 170 > h[1] , 170 < h[2] h[2] = 170第七个导弹 158 > h[1] , 158 < h[2] h[2] = 158第⼋个导弹 65 < h[1] 被第⼀个系统拦截 h[1] = 65

所以最后使⽤了两个系统就拦截了所有的导弹【遍历 h[]数组从 1到 n 看有⼏个 ！= INF 就说明使⽤了】

导弹⾼度：389 207 155 300 299 170 158 65

使⽤的拦截系统： 1 1 1 2 2 2 2 1 求最长上升⼦序列：

给定排好序的⼀堆数列中，求其的LIS长度。它的LIS长度就是它⾮上升⼦序列的个数。此题可以⽤N种⽅法讲解，下⾯⼀⼀为⼤家讲解：⽅法⼀：DP解法：

1 #include

2 #define MAX(x,y) x>y?x:y 3 int dp[10010],missile[10010]; 4 int main(){ 5 int N,max;

6 while(~scanf("%d",&N)){max=0; 7 for(int i=0;i

10 if(missile[j]

12 max=MAX(max,dp[i]);13 }

14 printf("%d\n",max);15 }

16 return 0;17 }

⽅法⼆：⼆分法+贪⼼：

1 #include

2 int missile[10010],Lis[10010]; 3 int r;

4 void search(int x){

5 int left=1,mid,right=r; 6 while(left<=right){

7 mid=(left+right)/2;//把 / 换成 >> ⽼是陷⼊死循环。。。。。

8 if(Lis[mid]

11 Lis[left]=x;12 }

13 int main(){14 int N;

15 while(~scanf("%d",&N)){r=1;

16 scanf("%d",&missile[0]);Lis[r]=missile[0];17 for(int i=1;i

18 scanf("%d",&missile[i]);

19 if(missile[i]>Lis[r])Lis[++r]=missile[i];20 else search(missile[i]);21 }

22 printf("%d\n",r);23 }

24 return 0;25 }

⽅法三：STL+⼆分+贪⼼：

STL+⼆分+贪⼼：

1 #include 2 #include 3 using namespace std; 4 int Lis[10010];

5 int main(){ 6 int N,r,x;

7 while(~scanf("%d",&N)){r=0; 8 scanf("%d",&x); 9 Lis[r]=x;

10 for(int i=1;i

12 if(x>Lis[r])Lis[++r]=x;

13 else *lower_bound(Lis,Lis+r,x)=x;

14 }

15 printf("%d\n",r+1);16 }

17 return 0;18 }

⽅法四：

vector+⼆分+贪⼼：

1 #include 2 #include 3 #include 4 using namespace std; 5 int main(){ 6 int N,x;

7 while(~scanf("%d",&N)){

8 vectorLis;vector::iterator iter; 9 while(N--){

10 scanf("%d",&x);

11 iter=lower_bound((),(),x);12 if(iter==())_back(x);13 else *iter=x;14 }

15 printf("%d\n",());16 }

17 return 0;18 }