AcWing 1010. 拦截导弹

题目传送门

一、Dilworth定理解法

1、Dilworth定理

最少的下降序列个数就等于整个序列最长上升子序列的长度

背下来这个定理结论吧！！！

2、实现代码

#include 

using namespace std;
const int N = 1010;
int n;      //导弹数量
int a[N];   //导弹高度
int f[N];   //以f[i]为结尾的最长不上升子序列，值为个数
int g[N];   //以g[i]为结尾的最长不下降子序列，值为个数
int ans1;   //最长不上升子序列的最大值 max(f[i])
int ans2;   //最长不上升子序列的最大值 max(g[i])

/*
一旦遇到上升的导弹就一定会用第二套导弹系统。没有其他方法能将上升序列的两个导弹一起打下来。
所以此题也就可以转化到最长下降子序列和最长上升子序列。
*/
int main() {
    while (cin >> a[n]) n++;

    for (int i = 0; i < n; i++) {
        f[i] = 1; //自己独立成序列
        g[i] = 1; //自己独立成序列
        for (int j = 0; j < i; j++) {
            if (a[i] <= a[j]) f[i] = max(f[i], f[j] + 1);//下降子序列
            else g[i] = max(g[i], g[j] + 1);//上升子序列
        }
        ans1 = max(ans1, f[i]);
        ans2 = max(ans2, g[i]);
    }
    //输出大吉
    printf("%d\n", ans1);
    printf("%d\n", ans2);
    return 0;
}

二、LIS+贪心

1、贪心策略

使用尽可能少的导弹拦截系统，拦截所有导弹。

(1)当出现新的敌方导弹时，我方从已有的拦截系统中，选取高度最低且可以拦截该导弹的那套系统，进行拦截。

(2)如果没有能拦截该导弹的拦截系统，则要新增一套拦截系统。

2、g数组为什么是单调递增的？

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

我们来模拟一下\(g\)数组变化情况：
(1) 讨论\(389\) \(g[0]=389\)
(2) 讨论\(207\) \(g[0]=207\)
(3) 讨论\(155\) \(g[0]=155\)

(4) 讨论\(300\) \(g[0]=155\)后面无法放下\(300\),需要再开启一个新的位置!
注意：这里首次放入的\(300\)，肯定是大于\(155\)的，否则不用开启新的位置！！！
\(g[0]=155\) \(g[1]=300\)

(5)讨论\(299\) \(g[0]=155\) \(g[1]=299\)
\(299\)之所以能替换了\(300\)，是因为它无法放在\(155\)的后面！整个数组的单调性不变！

(6)讨论\(170\) \(g[0]=155\) \(g[1]=170\)

(7)讨论\(158\) \(g[0]=155\) \(g[1]=158\)

(8)讨论\(65\) \(g[0]=65\) \(g[1]=158\)
\(65\)之所以能替换掉\(155\)，是因为它从左到右第一个就发现了合适的位置，使\(g[0]\)变的更小！整个数组的单调性不变！

结论：\(g\)数组是一个单调上升的序列。

3、实现代码

#include 

using namespace std;
const int N = 1010;
int n;      //n个导弹
int a[N];   //记录导弹飞行高度
int f[N];   //以f[i]为结尾的连续上升子序列的个数
int g[N];   //多套导弹防御系统的最后一个高度值(最矮的那个), 只需要记录最矮的即可。

int main() {
    //第一问
    while (cin >> a[n]) n++;//下标从0开始啊~

    //正常的LIS求最长不上升子序列
    int res = 0;
    for (int i = 0; i < n; i++) {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[i] <= a[j])f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    printf("%d\n", res);

    //第二问,求用几套导弹拦截系统可以完成拦截任务
    int cnt = 0;//使用的导弹拦截系统套数

    //遍历每个导弹
    for (int i = 0; i < n; i++) {
        //此导弹使用第几组导弹防御系统进行拦截？从前往后找的序列
        int k = 0;
        //搜索,因为g数组是单高的，所以找到第一个能装下a[i]的序列，就是目前导弹的最小高度~
        while (k < cnt && g[k] < a[i])k++;
        //如果没有任何一个序列存在大于等于当前数a[i]的，则需要创建一个新的序列
        if (k >= cnt) cnt++;
        //不管是否创建新的序列，都将a[i]放到此防御系统中
        g[k] = a[i];
    }
    //输出大吉
    printf("%d\n", cnt);
    return 0;
}

4、二分法优化版本

#include 

using namespace std;
const int N = 1010;
int n;      //n个导弹
int a[N];   //记录导弹飞行高度
int f[N];   //以f[i]为结尾的连续上升子序列的个数
int g[N];   //多套导弹防御系统的最后一个高度值(最矮的那个), 只需要记录最矮的即可。

int main() {
    //第一问
    while (cin >> a[n]) n++;//下标从0开始啊~

    //正常的LIS求最长不上升子序列
    int res = 0;
    for (int i = 0; i < n; i++) {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[i] <= a[j])f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    printf("%d\n", res);

    //数组g的每个元素代表一套导弹拦截系统的拦截序列
    //g[i]表示此时第i套导弹拦截系统所拦截的最后一个导弹的高度
    int cnt = 0;
    for (int i = 0; i < n; i++) { //遍历所有的导弹高度
        int k = lower_bound(g, g + cnt, a[i]) - g;
        if (k == cnt) g[cnt++] = a[i];  //a[i]开创一套新拦截系统
        else g[k] = a[i];               //a[i]成为第p套拦截系统最后一个导弹高度
    }
    //输出大吉
    printf("%d\n", cnt);
    return 0;
}