python/TangDou/AcWing/LIS/1010.md

##AcWing 1010. 拦截导弹

一、题目描述

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

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

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

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

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

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

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

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

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

输入样例：

389 207 155 300 299 170 158 65

输出样例：

6
2

二、问题解析

样例的图例：

Q1:最多拦截多少个导弹? 因为拦截系统第一下是可以任意高的，以后只能拦截和它一样高，或者比它矮的，所以，这是一个最长不上升子序列。

Q2:需要多少套拦截系统? 这一问有两种办法，按思考的由易到难，说明贪心法与定理法：

我们用两个贪心的证明方法来证明：

解释： Q:为什么一定可以放下去呢？ 答：因为x只能接在比它大的数字后面，由贪心法产生的序列，它前面是a,由最优解产生的序列，它前面是b,那么肯定有a>=x,b>=x，所以，是可以替换的。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int a[N], f[N]; // 每个导弹的高度，f[i]:以a[i]结尾的最长不升子序列长度
int q[N], ql;   // 需要ql套拦截系统，每个拦截系统最后一个拦截高度为q[i]
int n, res;

int main() {
    while (cin >> a[n]) n++;
    // 第一问
    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]);
    }
    // 第二问
    for (int i = 0; i < n; i++) {
        /* 1、现有已经创建了ql套导弹系统
           2、算法思路：
           (1) 在已有的所有导弹拦截系统中找到大于当前高度，并且最小的那个，把当前导弹用这套拦截系统进行拦截
           (2) 如果找不到这样的拦截系统，说明当前所有拦截系统的最小拦截高度都小于当前导弹，都无法利用，必须新开一个拦截系统。
           (3) 也就是说，只有前面拦截系统的最后一个拦截高度，都小于当前高度时，才会创建新的，所以，后面的拦截系统，它的尾巴值应该是最大的
           (4) 比如：
           q[0]:5
           q[1]:6
           现在来了一个高度=4,根据上面的原则，应该放到q[0]里，修改q[0]=4
           q[0]:4
           q[1]:6
           原来的数组是单调上升的，修改后也依然是单调上升的。

           再比如：
           q[0]:4
           q[1]:6
           q[2]:7
           现在来了一个a[i]=5,我们肯定要修改q[1]=5,变为：

           q[0]:4
           q[1]:5
           q[2]:7
           原来的数组是单调上升的，修改后也依然是单调上升的。

           既然有这个规律，那么就可以使用二分快速查找大于等于a[i]的位置p了：
        */
        int p = lower_bound(q, q + ql, a[i]) - q;
        if (p == ql) // 如果没有找到可以接在后面的导弹拦截系统，那么需要创建一套新的拦截系统
            q[ql++] = a[i];
        else
            q[p] = a[i]; // 否则就直接接到找到的第k套拦截系统的后面,那么，第k套拦截系统的最后一个拦截高度=q[k]=h[i]
    }
    // 输出最长不升序列长度,即：最多能拦截的导弹数
    printf("%d\n%d\n", res, ql);
    return 0;
}

Dilworth 定理

• 把序列分成不升子序列的最少个数，等于序列的最长上升子序列长度
• 把序列分成不降子序列的最少个数，等于序列的最长下降子序列长度

定理法

给定正整数序列，求最长不升子序列长度，以及能覆盖整个序列的不升子序列的最少个数

问题一 套用 LIS 模型即可求解。由 Dilworth 定理，问题二等价于 另一个 LIS 长度

Code

朴素作法 O(N^2)

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int n, a[N];
int f[N], fl;
int g[N], gl;

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); // 最长单调上升子序列的长度 = 不上升子序列的覆盖数
        }
        fl = max(fl, f[i]), gl = max(gl, g[i]);
    }
    printf("%d\n%d\n", fl, gl);
    return 0;
}