题目描述

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

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

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

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

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

样例

输入样例：
389 207 155 300 299 170 158 65
输出样例：
6
2

贪心的思路：

1. 枚举所有子序列的结尾，当所有的子序列的结尾都大于a[i]时候，创建一个新的序列
2. 接在第一个比a[i]小的子序列后面
   

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
int f[N],q[N];//g[i]存的是所有子序列结尾的数，g[i]一定是一个单调递增的序列
int main()
{
    int n=1;
    while(cin>>a[n])n++;
    n-=1;
    for(int i=n;i>=1;i--)
    {
        f[i]=1;
        for(int j=i+1;j<=n;j++)
            if(a[i]>=a[j])f[i]=max(f[i],f[j]+1);
    }
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,f[i]);
    cout<<res<<endl;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int k=0;
        while(k<cnt&&q[k]<a[i])k++;
        if(k==cnt)cnt++;
        q[k]=a[i];
    }
    cout<<cnt<<endl;
    return 0;
}