拦截导弹

题目概述：有一套导弹拦截系统，其每次可以拦截的导弹高度都不能高于上一次拦截导弹的高度。现在有一些导弹飞来，问这套系统最多能够拦截多少导弹，若想拦截所有的导弹，最少需要多少套系统。
解题思路：第一问就是典型的LIS模型。第二问的关键在于将某枚导弹归为哪一类下降子序列，从而使得使用的系统最少。这里直接给出贪心的结论和一个简单的证明：假设现在有k个下降子序列，将该枚导弹归为序列的结尾导弹高度不低于该枚导弹差值最小的下降序列最优。因为这样做可以使废弃的高度最小。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
const int N = 5010;

int num[N];
int g[N];//存储每个序列结尾导弹的高度
int dp[N];
int n;

void solve(){
	//输入导弹高度
	while(cin >> num[n])n++;

	int m = n;
	int ans = 0;

	int re = 0;
	for(int i = n - 1; i >= 0; i --){
		dp[i] = 1;
		for(int j = n - 1; j > i; j --){
			if(num[j] <= num[i])dp[i] = max(dp[i],dp[j] + 1);
		}
		re = max(re,dp[i]);
	}

	cout << re << endl;
	
	for(int i = 0; i < n; i ++){
	    int k = 0;
	    while(k < ans && g[k] < num[i])k++;
	    if(k == ans)g[ans++] = num[i];
	    else g[k] = num[i];
	}
	
	cout << ans << endl;
	
}

int main(){
	int T = 1;

	while(T --){
		solve();
	}
	
}