洛谷P1020 导弹拦截 最长不上升子序列 及其优化

P1020 导弹拦截

第一问，相当于求一个最长不上升子序列。

第二问，相当于求一个最长上升子序列

证明如下：

• 假设打导弹的方法是这样的：取任意一个导弹，从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组，再在没打下来的导弹中任选一个重复上述步骤，直到打完所有导弹。
• 假设我们得到了最小划分的K组导弹，从第a(1<=a<=K)组导弹中任取一个导弹，必定可以从a+1组中找到一个导弹的高度比这个导弹高（因为假如找不到，那么它就是比a+1组中任意一个导更高，在打第a组时应该会把a+1组所有导弹一起打下而不是另归为第a+1组），同样从a+1组到a+2组也是如此。那么就可以从前往后在每一组导弹中找一个更高的连起来，连成一条上升子序列，其长度即为K;
• 设最长上升子序列长度为P，则有K<=P;又因为最长上升子序列中任意两个不在同一组内(否则不满足单调不升)，则有
• P>=K，所以K=P。

来源：https://jjpjj.blog.luogu.org/dp-dao-tan-lan-jie

n*n的解法

int d[N];//d[i]表示以第i个数结尾的最长不上升子序列的长度
int dp[N];//dp[i]表示以第i个数结尾的最长上升子序列的长度


d[0] = 1e9;
int ma1 = 0, ma2 = 0;
for(int i = 1; i <= cnt; i++){
	for(int j = 0; j < i; j++){//对于a[i]，在前i个数找到不大于a[i]的，d[i]=max(d[i], d[j]+1)
		if(a[i] <= a[j]) d[i] = max(d[i], d[j]+1);
	}
	ma1 = max(ma1, d[i]);
	for(int j = 0; j < i; j++){
		if(a[i] > a[j]) dp[i] = max(dp[i], dp[j]+1);
	}
	ma2 = max(ma2, dp[i]);
}

nlogn解法，二分优化

用d[i]表示长度为 l 的不上升子序列最后一个数。

对于每个数a[i] ，

如果a[i] <= d[l] ， 那么可以直接将 a[i] 加在 d[l] 后面。

否则，在数组d内找到第一个小于a[i]的d，用a[i] 替换d

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;

int a[N];
int d[N];//d[i]表示长度为i的不上升子序列最后一个数
int dp[N];
int main(){
	int cnt=1;
	while(~scanf("%d",&a[cnt])){
		cnt++;
	}
	d[0] = 1e9;
	dp[0] = 0;
	int l1=0,l2=0;
	int pos;
	for(int i = 1; i < cnt ; i++){
		if(a[i] <= d[l1]){
			d[++l1] = a[i];
		}
		else {
			pos = upper_bound(d, d+l1, a[i],greater<int>())-d;
			d[pos] = a[i];
		}
		if(a[i] > dp[l2]){
			dp[++l2] = a[i];
		}
		else {
			pos = lower_bound(dp,dp+l2, a[i])-dp;
			dp[pos] = a[i];
		}
	}
	cout << l1 << endl << l2 << endl;
	return 0;
}