AcWing 1010. 拦截导弹

题目描述

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

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

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

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

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

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

样例

输入:
389 207 155 300 299 170 158 65

输出：
6
2

解释：
最少可以配2个系统，其中最长的序列长度是6
389 300 299 170 158 65
207 155

限制

$ 1 ≤ N ≤ 1000 $
$ 0 ≤ 导弹高度 ≤ 30000 $

算法1

LIS 是 Longest ascending subsequence 的缩写

(LIS+贪心) $O(n^2)$

• 第一问思路和AcWing 895. 最长上升子序列一样；
• 第二问思路和AcWing 896. 最长上升子序列 II一样；为什么呢？
  • 因为至少需要多少个下降子序列的数目的思路和它真的很像
  • 贪心思路：较大的数末尾元素比较小的数作为末尾元素的子序列更好.
  • 贪心步骤：
    • 开一个q[]记录所有下降子序列末尾元素，q[]一开始是空集，长度为0
    • 遍历每个数，对于当前这个数：
      • 情况1：在q[]中若找不到比这个数更小的数，扩大q[]长度并记录这个数
      • 情况2：在q[]中可以找到比这个数小的最大的数, 则将它覆盖到所找到的位置上
    • 可以证明q[]必定是一个单调上升的数组
      • 一开始q[]是空集, 空集也是单调的一种
      • 对于每个数x要记录到q[]时, 存在一个不等式c > x ≥ a ≥ b, 其中a是将要被x覆盖的数, 因为a是比x小的最大的数
      • 覆盖之后就会变成c > x ≥ b, 并不改变q[]的单调性, 且q[]是
    • 每次将一个较小的数换成一个较大的数作为末尾元素存储到q[], 随着q[]的长度扩大, 也就表示此时新增x比所有末尾元素都大时; q[]随下标增大元素值也越大, 因此q[]是单调上升的数组
  • 结论：
    • 此题思路和AcWing 896. 最长上升子序列 II 一模一样，因此求解至少需要多少个下降子序列的数目 和求解至多含有多少个上升子序列的数目是一个对偶问题
    • 对于记录末尾元素是q[]
      • 若存储上升子序列的q[]: 随下标增大, 数组元素越小
      • 若存储下降子序列的q[]: 随下标增大, 数组元素越大

时间复杂度

• 第一问的时间复杂度是：$O(n^2)$
• 第二问：
  • 遍历n个数是：$O(n)$
  • 找到第一个最大的比a[i]小的值最坏是：$O(n)$
  • 因此第二问的时间复杂度是：$O(n^2)$

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int n;
int a[N], g[N], f[N];

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

    int res = 0;
    for(int i = 0; i < n; i ++) {
        f[i] = 1;

        for(int j = 0; j < i; j ++)
            if(a[j] >= a[i])                // 不高于, 可以等于， 最长下降子序列
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    int len = 0;
    for(int i = 0; i < n; i ++){
        int k = 0;
        while(k < len && g[k] < a[i]) k ++; // 从左往右开始找, 找到第一个最大的比a[i]小的值
        g[k] = a[i];
        if(k >= len) len ++;
    }

    cout << res << endl;
    cout << len << endl;
    return 0;
}

算法2（基于算法1）

(LIS+贪心) $O(n^2)$

• 基于算法1的另一种写法
• 将AcWing 895. 最长上升子序列，分别默写2遍
  • 其实AcWing 896. 最长上升子序列 II 只是比最长上升子序列 I的数值范围大，而在本题数值范围允许的情况下，使用2次最长上升子序列 I也ok的
• 即理解为 给定一个序列，求至少包含多少个下降子序列数目等价于给定一个序列，求至多包含多少个上升子序列数目

时间复杂度

• 第一问的时间复杂度是：$O(n^2)$
• 第二问的时间复杂度是：$O(n^2)$
• 因此时间复杂度：$O(n^2)$

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int n;
int a[N], f[N];

int main()
{
    // 第一问：问题是求最长下降子序列的长度
    while(cin >> a[n])n++;
    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]);
    }

    // 第二问：问题转化为求解最长上升子序列的长度
    int len = 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);
        len = max(len, f[i]);
    }

    cout << res << endl;
    cout << len << endl;
    return 0;
}

算法3（基于算法1）

(LIS+贪心+二分) $O(n^2)$

• 只是针对找到最大的比a[i]小的值使用二分优化为$O(logn)$

时间复杂度

• 第一问的时间复杂度是：$O(n^2)$
• 第二问的时间复杂度是：$O(nlogn)$
• 因此时间复杂度：$O(n^2)$

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N], f[N], q[N];

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

    int res = 0;
    for(int i = 0; i < n; i ++){
        f[i] = 1;

        for(int j = 0; j < i; j ++)
            if(a[j] >= a[i])        // 最长下降子序列
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    int len = 0;
    for(int i = 0; i < n; i ++){
        int l = 0, r = len;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        q[r + 1] = a[i];
        len = max(len, r + 1);
    }

    cout << res << endl;
    cout << len << endl;
    return 0;
}