1010. 拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

共一行，输入导弹依次飞来的高度。

输出格式

第一行包含一个整数，表示最多能拦截的导弹数。

第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。

数据范围

雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。

输入样例：

389 207 155 300 299 170 158 65

输出样例：

6
2

题解

NOIP很经典的一道题，共有两问，两问之间并无太大联系，完全可以当作两个题做。

第一问是经典的最长上升子序列模型，只不过这里需要求最长不下降子序列，按照题意去套板子就可以了，复杂度是n方。

第二问就是一个典型的贪心，在这里简单证明一下：

假设我们先把该队列按照题意分为k个队列，如果某一组的最低高度（也就是队尾元素）高于另一队列的最高高度（队首元素），那么这两个队列应该合并，结果k与题意不符；由上一点我们可以知道，如果a序列的队尾元素，大于b序列内的任意一个元素，那么也能将该元素到其队尾全部合并到a序列中，不会改变结果。

因此，我们的贪心思路是先遍历整个序列，把所有能加入的元素加入队列组成一个不下降序列，然后删去这些元素，对答案加一；重复该步骤直到队列中没有元素。

代码

#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int> 
using namespace std;

const int N=1005;
int dp[N],a[N];
void solve()
{
	int n=0;
	do{
		n++;
	}while(cin>>a[n]);
	n--;
	for(int i=1;i<=n;i++)
	{
		dp[i]=1;
		for(int j=1;j<i;j++)
		{
			if(a[i]<=a[j]) dp[i]=max(dp[i],dp[j]+1);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i]);
		dp[i]=0;
	}
	cout<<ans<<endl;
	ans=0;
	while(1)
	{
		int x=-1;
		for(int i=1;i<=n;i++)
		{
			if(dp[i]==0)
			{
				if(x<0)
				{
					dp[i]=1;
					x=a[i];
				}
				else 
					if(x>=a[i]){
						dp[i]=1;
						x=a[i];
					}
			}
		}
		if(x==-1) break;
		ans++;
	}
	cout<<ans;
}
int main()
{
	int T=1;
	//cin>>T; 
	while(T--)
	{
		solve();
	}
	return 0;
}