死嗑最长上升子序列（LIS）

灰太狼 2022-11-21 15:22 177阅读 0赞

### [**【模板】LIS**][LIS] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center]

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=1e5+10;
    int a[N],f[N]; // f[i]：上升子序列长度为 i 的最小末尾数值
    
    int main()
    { 
    	int n;cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	int len=1;f[1]=a[1];
    	for(int i=2;i<=n;i++)
    	{ 
    		if(f[len]<a[i]) f[++len]=a[i];
    		else 
    		{ 
    			// 二分查找（手写）
    			int l=1,r=len,mid;
    			while(l<r)
    			{ 	
    			    mid=(l+r)/2;
    			    if(f[mid]>a[i])r=mid;
    				else l=mid+1; 
    			}
    			f[l]=a[i];
    			/* 二分查找（函数） int tmp=lower_bound(f+1,f+1+len,a[i])-f; f[tmp]=a[i]; */
    		}
    	 	//for(int j=1;j<=i;j++) cout<<f[j]<<' '; //打印
    	 	//cout<<" len:"<<len<<endl; //打印长度
    	}
    	cout<<len<<endl;
    	return 0;
    }

**思路**  
我们用DP思想来维护一个栈 `f`，如果 `a[i] > a[i-1]`，则将 `a[i]` 放入栈 `f` 中。否则，二分查找栈 `f` 中大于 `a[i]` 的最小的数，并将它替换。长度为  l e n len len 的栈 `f` 是目前序列下的最佳  L I S LIS LIS（并非唯一）

下面是每层循环（`i++`）后的栈 `f` 里的各值（此处的  I N F INF INF 只是为了凑齐  i i i 个数字）

a[7] =	1 3 2 7 4 5 6
    
    i = 1	1					len: 1
    i = 2	1 3					len: 2
    i = 3	1 2 INF				len: 2
    i = 4	1 2 7 INF			len: 3
    i = 5	1 2 4 INF INF		len: 3
    i = 6	1 2 4 5 INF INF		len: 4
    i = 7	1 2 4 5 6 INF INF	len: 5
    
    //如果当前 f 数组不是最佳 LIS，甚至 f[1] 的值 1 都可以换掉（为了替换成最佳）

**替换**  
二分查找的手写版可以替换为函数版，不懂 lower\_bound 函数的点[**这里**][Link 1]

//举例
    f[4] = 0 1 3 2
    
    lower_bound(f+1,f+2,2)-f; //值 1 和 3 哪个大于等于 2 就返回它的下标（下标是从 1 开始计数）
    output:2

### [**导弹拦截**][Link 2] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 1]

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=1e5+10;
    int a[N],f1[N],f2[N],n=0;
    
    int main()
    { 
    	while(cin>>a[++n]); n--;
    	
    	//最长不上升序列
    	int len1=1;f1[1]=a[1];
    	for(int i=2;i<=n;i++)
    	{ 
    		if(f1[len1]>=a[i]) f1[++len1]=a[i];
    		else { 
    			int tmp=upper_bound(f1+1,f1+1+len1,a[i],greater<int>())-f1;
    			f1[tmp]=a[i];
    		}
    	}
    	cout<<len1<<endl;
    	
    	//最长上升序列（LIS）
    	int len2=1;f2[1]=a[1];
    	for(int i=2;i<=n;i++)
    	{ 
    		if(f2[len2]<a[i]) f2[++len2]=a[i];
    		else { 
    			int tmp=lower_bound(f2+1,f2+1+len2,a[i])-f2;
    			f2[tmp]=a[i];
    		}
    	}
    	cout<<len2<<endl;
    	
    	return 0;
    }

**思路**  
第一问 显然是求最长不上升序列  
第二问 是求最长上升序列（LIS），两种思路如下：  
**1、** 打个比方，突然有一个导弹的高度大于你当前的拦截最大高度，你肯定拦截不了，所以你肯定需要再来一个系统才能拦截下来。所以只需求最长上升子序列的长度即是需要的系统数量  
**2、**  
① 假设打导弹的方法是这样的：取任意一个导弹，从这个导弹开始将能打的导弹全部打完，而这些导弹全部记为为同一组，再在没打下来的导弹中任选一个重复上述步骤，直到打完所有导弹  
② 假设我们得到了最小划分的  K K K 组导弹，从第  a ( 1 ≤ a ≤ K ) a(1≤a≤K) a(1≤a≤K) 组导弹中任取一个导弹，必定可以从  a + 1 a+1 a\+1 组中找到一个导弹的高度比这个导弹高（因为假如找不到，那么它就是比  a + 1 a+1 a\+1 组中任意一个导更高，在打第  a a a 组时应该会把  a + 1 a+1 a\+1 组所有导弹一起打下而不是另归为第  a + 1 a+1 a\+1 组），同样从  a + 1 a+1 a\+1 组到  a + 2 a+2 a\+2 组也是如此，那么就可以从前往后在每一组导弹中找一个更高的连起来，连成一条上升子序列，其长度即为  K K K  
③ 设最长上升子序列长度为  P P P，则有  K < = P K<=P K<=P，又因为最长上升子序列中任意两个不在同一组内(否则不满足单调不升)，则有  P > = K P>=K P>=K，所以  K = P K=P K=P

**最长 上升/不下降/下降/不上升序列 模板**

const int N=1e5+10;
    int a[N],f1[N],f2[N],f3[N],f4[N];
    
    //最长上升序列（LIS）
    int len1=1;f1[1]=a[1];
    for(int i=2;i<=n;i++)
    { 
    	if(f1[len1]<a[i]) f1[++len1]=a[i];
    	else { 
    		int tmp=lower_bound(f1+1,f1+1+len1,a[i])-f1;
    		f1[tmp]=a[i];
    	}
    }
    cout<<len1<<endl;
    
    
    //最长不下降序列
    int len2=1;f2[1]=a[1];
    for(int i=2;i<=n;i++)
    { 
    	if(f2[len2]<=a[i]) f2[++len2]=a[i];
    	else { 
    		int tmp=upper_bound(f2+1,f2+1+len2,a[i])-f2;
    		f2[tmp]=a[i];
    	}
    }
    cout<<len2<<endl;
    
    
    //最长下降序列
    int len3=1;f3[1]=a[1];
    for(int i=2;i<=n;i++)
    { 
    	if(f3[len3]>a[i]) f3[++len3]=a[i];
    	else { 
    		int tmp=lower_bound(f3+1,f3+1+len3,a[i],greater<int>())-f3;
    		f3[tmp]=a[i];
    	}
    }
    cout<<len3<<endl;
    
    
    //最长不上升序列
    int len4=1;f4[1]=a[1];
    for(int i=2;i<=n;i++)
    { 
    	if(f4[len4]>=a[i]) f4[++len4]=a[i];
    	else { 
    		int tmp=upper_bound(f4+1,f4+1+len4,a[i],greater<int>())-f4;
    		f4[tmp]=a[i];
    	}
    }
    cout<<len4<<endl;

### [**合唱队形**][Link 3] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 2]

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=1e3+10;
    int a[N],f1[N],f2[N],ans1[N],ans2[N];
    
    int main()
    { 
    	int n;cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	int len1=1;f1[1]=a[1];ans1[1]=1; //顺序 LIS
    	for(int i=2;i<=n;i++)
    	{ 
    		if(f1[len1]<a[i]) f1[++len1]=a[i];
    		else { 
    			int tmp=lower_bound(f1+1,f1+1+len1,a[i])-f1;
    			f1[tmp]=a[i];
    		}
    		ans1[i]=len1;
    	}
    	int len2=1;f2[1]=a[n];ans2[n]=1; //逆序 LIS
    	for(int i=n-1;i>=1;i--)
    	{ 
    		if(f2[len2]<a[i]) f2[++len2]=a[i];
    		else { 
    			int tmp=lower_bound(f2+1,f2+1+len2,a[i])-f2;
    			f2[tmp]=a[i];
    		}
    		ans2[i]=len2;
    	}
    	//for(int i=1;i<=n;i++) cout<<ans1[i]<<' '<<ans2[i]<<endl;
    	int minn=INT_MAX;
    	for(int i=1;i<=n;i++) minn=min(minn,n-(ans1[i]+ans2[i]-1));
    	cout<<minn<<endl;
    	return 0;
    }

**思路**  
我们想一想，要想使  T i ( 1 ≤ i ≤ K ) T\_i(1≤i≤K) Ti(1≤i≤K) 满足左边和右边都是递减，那么左边的每个元素的最长上升序列就是它的下标（从  1 1 1 开始），右边同理，左右两边元素一直到  T i T\_i Ti 的最长上升序列之和减一（去除重复）就是  K K K（总人数）；举个例子，要是左边的某个元素不满足最长上升序列，那么左边一直到  T i T\_i Ti 的和就少了  1 1 1，右边不变，最后总和也相比  K K K 少了  1 1 1，若是把这个人给去掉，才满足题意，所以最后答案就是  1 1 1

我们先看从  T 1 T\_1 T1 到  T i T\_i Ti 这一段单调递增的序列，再看  T i T\_i Ti 到  T K T\_K TK 这一段单调递减的序列，那么问题就解决了，先从  1 1 1 到  n n n 求一趟最长上升序列的  l e n len len 并用数组  a n s 1 ans1 ans1 保存，然后从  n n n 到  1 1 1 也求一趟并用数组  a n s 2 ans2 ans2 保存，最后枚举全部的  a n s 1 + a n s 2 − 1 ans1+ans2-1 ans1\+ans2−1（去除重复），因为想出列最少，那么就想要留下的最多，从中最小的  n − ( a n s 1 + a n s 2 − 1 ) n-(ans1+ans2-1) n−(ans1\+ans2−1) 即答案

**注意**  
逆序  L I S ≠ LIS\\neq LIS= 最长下降序列，因为它们每个元素  l e n len len 的不同

### [**Super Jumping! Jumping! Jumping!**][Super Jumping_ Jumping_ Jumping] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 3]

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=1e5+10;
    int a[N],f[N],ans[N],maxn;
    
    //f[i] 以目前元素为末尾的 LIS长度，并非整个序列的 LIS长度
    //ans[i] 以目前元素为末尾的上升序列的最大递增字段和，并非整个序列的最大递增字段和 
    
    int main()
    { 
    	int n;
    	while(~scanf("%d",&n),n>0)
    	{ 
    		memset(f,0,sizeof(f));
    		memset(ans,0,sizeof(ans));
    		maxn=0;
    		for(int i=1;i<=n;i++) cin>>a[i];
    		f[1]=1;ans[1]=a[1];
    		for(int i=2;i<=n;i++) { 
    			for(int j=1;j<i;j++) { 
    				if(a[i]>a[j]) { 
    					f[i]=max(f[i],f[j]+1);
    					ans[i]=max(ans[i],ans[j]+a[i]);
    				}
    			}
    		}
    		for(int i=1;i<=n;i++) { 
    			//cout<<f[i]<<' ';
    			maxn=max(maxn,ans[i]);
    		}
    		cout<<maxn<<endl;
    	}
    	return 0;
    }

**思路**  
 n 2 n^2 n2的做题思路。注意 `ans[i]` 并不是所有序列中的最大递增字段和，`f[i]` 同理不是所有序列中的最大  L I S LIS LIS 长度【本题并没有要求算 `f[i]`，我只是单纯的列个模板】

### [**FatMouse’s Speed**][Super Jumping_ Jumping_ Jumping] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 4]

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=1e5+10;
    int f1[N],f2[N],ans1[N],ans2[N];
    
    struct Node { 
    	int weight,speed,num;
    }node[N];
    
    bool cmp1(Node &a,Node &b)
    { 
    	if(a.weight!=b.weight) return a.weight<b.weight;
    	else return a.speed<b.speed;
    }
    
    bool cmp2(Node &a,Node &b)
    { 
    	if(a.speed!=b.speed) return a.speed<b.speed;
    	else return a.weight>b.weight;
    }
    
    int main()
    { 
    	int a,b,n=1;
    	while(~scanf("%d %d",&a,&b)!=EOF)
    	{ 
    		node[n].weight=a;
    		node[n].speed=b;
    		node[n].num=n; //不能写成 n++ 
    		n++;
    	}
    	sort(node+1,node+n,cmp1);
    	f1[1]=node[1].speed;ans1[1]=node[1].num;int len1=1;
    	for(int i=2;i<n;i++)
    	{ 
    		if(f1[len1]>=node[i].speed) { 
    			f1[++len1]=node[i].speed;
    			ans1[len1]=node[i].num;
    		}
    		else
    		{ 
    			int tmp=upper_bound(f1+1,f1+1+len1,node[i].speed,greater<int>())-f1;
    			f1[tmp]=node[i].speed;
    			ans1[tmp]=node[i].num;
    		}
    	}
    	/* for(int i=1;i<n;i++) { cout<<node[i].weight<<' '<<node[i].speed<<' '<<node[i].num<<endl; } cout<<endl; */
    	sort(node+1,node+n,cmp2);
    	f2[1]=node[1].weight;ans2[1]=node[1].num;int len2=1;
    	for(int i=2;i<n;i++)
    	{ 
    		if(f2[len2]<=node[i].weight) { 
    			f2[++len2]=node[i].weight;
    			ans2[len2]=node[i].num;
    		}
    		else
    		{ 
    			int tmp=upper_bound(f2+1,f2+1+len2,node[i].weight)-f2;
    			f2[tmp]=node[i].weight;
    			ans2[tmp]=node[i].num;
    		}
    	}
    	/* for(int i=1;i<n;i++) { cout<<node[i].weight<<' '<<node[i].speed<<' '<<node[i].num<<endl; } */
    	cout<<((len1>len2)?len1:len2)<<endl;
    	if(len1>len2)
    		for(int i=1;i<=len1;i++)
    			cout<<ans1[i]<<endl;
    	else
    		for(int i=1;i<=len2;i++)
    			cout<<ans2[i]<<endl;
    	return 0;
    }

**思路**  
这道简单题花了我一个下午你信不信？  
整体思路非常简单，先将结构体先按照体重递增排序，再对排好的序列的速度进行求最长不上升序列，得到 `len1`；再将结构体先按照速度递减排序，再对排好的序列的体重进行求最长不下降序列，得到 `len2`；最后比较两者哪个大就取哪个的 `ans[i]`（最长不上升/不下降序列）作为结果

但是！其中包含许多细节，比如赋值时的 `=n; n++` 不能直接写成 `=n++` **（我也不知道为什么）** ，又比如 sort 括号内的 `+n` 而不是 `+n-1`（因为是从下标1开始赋值的），再比如最开始 `while(~scanf(...)!=EOF)` 的运用。总而言之，这道题算是考察到了很多知识点，也考察了细心程度，有机会的话，可以再做一次加深印象 **（相信你做完之后对  L I S LIS LIS 的理解程度可以更上一层）**

**回顾（结构体的 sort 用法）**  
下面两种方法经排序得出的结果都是【体重严格递增，若体重相同则速度严格递减】

//结构体内含 cmp函数
    
    struct Node { 
    	int weight,speed;
    	bool operator < (const Node &b)const
    	{ 
    		if(weight!=b.weight) return weight<b.weight;
    		else return speed<b.speed;
    	}
    }node[N];
    
    sort(node,node+n);
    
    
    //结构体外含 cmp函数
    
    struct Node { 
    	int weight,speed;
    }node[N];
    
    bool cmp(Node &a,Node &b)
    { 
    	if(a.weight!=b.weight) return a.weight<b.weight;
    	else return a.speed<b.speed;
    }
    
    sort(node,node+n,cmp);

[LIS]: https://www.luogu.com.cn/problem/AT2827
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/7662696d8f3b4222b63a899a615c9c62.png
[Link 1]: https://blog.csdn.net/CourserLi/article/details/105652435
[Link 2]: https://www.luogu.com.cn/problem/P1020
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/0f4743da23a44a1babaed054d8a523ee.png
[Link 3]: https://www.luogu.com.cn/problem/P1091
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/66f1917718d74d3a83afc69bc376eb71.png
[Super Jumping_ Jumping_ Jumping]: https://blog.csdn.net/lxt_Lucia/article/details/81206439
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/a27018e6a46b4ffa9db4d38c0fe10a6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/a384813239174f71897f5cded5998e5a.png