题目描述

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

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入 #1

389 207 155 300 299 170 158 65

输出 #1

6
2

说明/提示

对于前 50% 数据（NOIP 原题数据），满足导弹的个数不超过 104 个。该部分数据总分共 100 分。可使用O(n2) 做法通过。
对于后 50% 的数据，满足导弹的个数不超过 105 个。该部分数据总分也为 100 分。请使用 O(nlogn) 做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过 5×104。

此外本题开启 spj，每点两问，按问给分。

NOIP1999 提高组 第一题

---

upd 2022.8.24：新增加一组 Hack 数据。

思路：

对于第一问，我们即是要求出最长不上升子序列。

对于第二问，我们需要多少个系统，我们即是要求最长上升子序列，因为在这个子序列中，每一个前面的数都不可能和后面的一个数在一个系统中，所以我们需要将每个数都分到不同的系统中。所以最长上升子序列便是系统数。

#include<bits/stdc++.h>
using namespace std;

typedef struct Group{
	int x,y;
//	bool operator<(Group g) const{
//		if(x!=g.x) return x<g.x;
//		else return y<g.y;
//	}	
}G;
typedef long long ll;
const int mod = 1e6+7;
int n,m;
int r,c;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int x;
	vector<int> nums;
	
	while(cin>>x){
		nums.push_back(x);
	}
	
	int length = nums.size();
	vector<int> dp(length,1);
	
	int res = -1;
	for(int i=0; i<length; i++){
		for(int j=i-1; j>=0; j--){
			if(nums[i]<=nums[j]) dp[i] = max(dp[i],dp[j]+1);			
			res = max(dp[i],res);
		}
	}
	cout<<res<<endl;
	
	res = -1;
	vector<int> dp2(length,1);
	for(int i=0; i<length; i++){
		for(int j=i-1; j>=0; j--){
			if(nums[i]>nums[j]) dp2[i] = max(dp2[i], dp2[j]+1);
			res = max(dp2[i],res);
		}
	}
	cout<<res<<endl;
	return 0;
}

优化：

我们如果单纯用动态规划，时间复杂度是n的平方，我们考虑到可以将内部循环进行优化，使用二分查找。

对于第一问

我们维护一个数组len[i]，表示最长不上升子序列长度为i时，结尾的数最大值为len[i]，我们可以知道len数组是单调不增的。

同理第二问。

我们维护一个数组len2[i]，表示最长上升子序列长度为i时，结尾的数最小值为len2[i]，我们可以知道len数组时单调递增的。

#include<bits/stdc++.h>
using namespace std;

typedef struct Group{
	int x,y;
//	bool operator<(Group g) const{
//		if(x!=g.x) return x<g.x;
//		else return y<g.y;
//	}	
}G;
typedef long long ll;
const int mod = 1e6+7;
int n,m;
int r,c;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int x;
	vector<int> nums;
	
	while(cin>>x){
		nums.push_back(x);
	}
	
	int length = nums.size();
//	vector<int> dp(length,1);
	
	vector<int> len(length+1,-1);
	len[0] = INT_MAX;
	int res=-1;
	for(int i=0; i<length; i++){
		
//		for(int j=i-1; j>=0; j--){
//			if(nums[i]<=nums[j]) dp[i] = max(dp[i],dp[j]+1);			
//			res = max(dp[i],res);
//		}
		
		int l=0, r=length;
		while(l<=r){
//			cout<<l<<" "<<r<<endl;
			int mid = l + (r-l)/2;
			if(len[mid]>=nums[i]) l=mid+1;
			else r=mid-1;
//			cout<<l<<" "<<r<<endl;
		}
		len[l] = nums[i];
		res = max(l,res);
	}
	cout<<res<<endl;
	
	res = -1;
//	vector<int> dp2(length,1);
	vector<int> len2(length+1, INT_MAX);
	len2[0] = -1;
	for(int i=0; i<length; i++){
//		for(int j=i-1; j>=0; j--){
//			if(nums[i]>nums[j]) dp2[i] = max(dp2[i], dp2[j]+1);
//			res = max(dp2[i],res);
//		}
		int l=0, r=length;
		while(l<=r){
			int mid = l + (r-l)/2;
			if(nums[i]>len2[mid]) l=mid+1;
			else r = mid-1;
//			cout<<l<<" "<<r<<" "; 
		}
//		cout<<endl;
		len2[l] = nums[i];
		res = max(res,l);
	}
	cout<<res<<endl;

	return 0;
}