导弹拦截 题解

根据题目描述：导弹依次飞来，拦截时每一发炮弹都不能高于前一发的高度。那么最多能拦截的导弹数，其实就是最长的下降（非严格下降）子序列的长度。

第二问求最少要配备多少套这种导弹拦截系统？可以使用贪心思想，流程如下：
从前向后遍历每一个导弹高度，对于每一个数来说，有两种情况：

1. 所有拦截系统的最低高度都小于当前导弹高度，需要增加一套系统
2. 找到第一套系统，其拦截的最低高度大于等于当前导弹的高度，更新该系统的最低拦截高度。

AC代码

#include <iostream>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int a[N], f[N], b[N];
int main(){
    int n = 0, x;
    while(cin>>x) a[++n] = x;
    int res = 0;
    for(int i = 1; i <= n; i++){
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[j] >= a[i]) f[i] = max(f[i], f[j] + 1);
        }
        if(res < f[i]) res = max(res, f[i]);
    }
    cout<<res<<endl;
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        int k = 0; 
        //b[k]表示第k套拦截系统能够拦截的最小高度，并且b[]序列一定是严格单调递增的
        while(k < cnt && b[k] < a[i]) k++;
        if(k >= cnt) cnt++;
        b[k] = a[i];        
    }
    cout<<cnt<<endl;
    return 0;
}