题目描述:

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

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

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

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

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

输入格式：

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

输出格式：

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

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

数据范围：

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

输入样例：

389 207 155 300 299 170 158 65

输出样例：

6
2

算法思路：

题目共有两部分，第一部分相当于求序列的最长下降子序列，第二部分则需要运用贪心的思想。下面分开详细讲解。

1.最长下降子序列：

最长下降子序列实际上是一种dp问题。

状态标识：f [ i ]： 表示在序列中以 i 结尾的所有下降子序列集合中的最长下降子序列的长度。

状态转移：f [ i ]  = max( f [ i ], f [ j ] + 1)； i表示当前遍历到的序列位置，j表示在i之前的某个数。

                 解释：因为f [ i ] 表示的下降子序列以i结尾，状态转移选择的应该为状态改变的位置，故我们选择i之前一个数作为状态改变的判断位置。在遍历 j 的过程中，f [ j ] 表示的一定是以 j 结尾的下降子序列的长度，所以，如果发现小于i，我们应该更新f [ i ] 的值。

第一问部分的代码：

//q[i]表示导弹的高度序列
//res表示答案，即最长下降子序列的长度
//f[i]记录以i结尾的下降子序列的最大长度
    int res = 0;
    for(int i = 0; i < n; i ++ ){
        f[i] = 1;
        for(int j = 0; j < i; j ++ )
            if(q[j] >= q[i]) 
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    cout << res << endl;

2.第二问贪心思路：

1。当遍历到一个导弹飞来的高度时，有两种供选择的方案：

1）选择大于该导弹高度的最小的高度，添加在该序列之后。

2）所有序列的末尾导弹高度均小于改导弹高度，创建新序列。

2.使用g [  ] 存放每个导弹序列的末尾导弹高度，我们可以发现，g [ ] 一定是单调递增的。

第二问代码：

    //cnt表示导弹序列个数
    int cnt = 0;
    for(int i = 0; i < n; i ++ ){
        int k = 0;
        while(k < cnt && g[k] < q[i])   k ++ ;
        g[k] = q[i];
        if(k >= cnt) cnt ++ ;
    }

    cout << cnt << endl;

完整AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n;
int q[N];
int f[N], g[N];

int main(){
    while(cin >> q[n]) n ++ ;

    int res = 0;
    for(int i = 0; i < n; i ++ ){
        f[i] = 1;
        for(int j = 0; j < i; j ++ )
            if(q[j] >= q[i]) 
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    cout << res << endl;

    int cnt = 0;
    for(int i = 0; i < n; i ++ ){
        int k = 0;
        while(k < cnt && g[k] < q[i])   k ++ ;
        g[k] = q[i];
        if(k >= cnt) cnt ++ ;
    }

    cout << cnt << endl;

    return 0;
}