某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于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;
}