AcWing 1010. 拦截导弹（最长上升子序列 + 贪心）

题目链接

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

题目模型

• 最长上升子序列
• 贪心
  
  证明A≤B用调整法：
  
  因为b≥a，所以可以交换x后面的序列，且不增加总的序列个数，即A≤B
• Ddilworth定理：最小链覆盖数 = 最长反链长度，即最少用多少个非下降子序列把它覆盖掉的数量等于最长上升子序列的长度。

题目代码

#include 
#include 
#include 

using namespace std;

const int N = 1010;

int n;
int q[N];
int f[N], g[N];  //g数组用来存所有序列的最后一个元素, 且元素单调递增

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[i] <= q[j])
                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数组中
        g[k] = q[i];
        if(k >= cnt) cnt ++;
    }
    
    cout << cnt << endl;
    
    return 0;
}