动态规划系列 | 最长上升子序列模型（下）| 拦截导弹一网打尽！

拦截导弹

题目描述

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

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

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

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

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

输入格式

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

输出格式

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

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

问题分析

第一问

求最多能拦截的导弹数量，其实就是求最长上升子序列问题的变形。

求的是最长下降子序列，且子序列中的元素可以相等。

第二问

采用贪心的策略：

• 情况 1：如果现有的子序列的结尾都小于当前数，则创建新子序列
• 情况 2：存在一些子序列的结尾大于等于当前数，则将当前数放到这些子序列中，结尾数最小的子序列后面。

贪心正确性证明

证明：贪心解 >= 最优解

贪心算法得到的系统个数一定大于等于最优解的个数。

证明：贪心解 <= 最优解

假设最优解对应的方案与贪心得到的方案不同，则一定能找到一个数，分配的序列不同。

由于贪心法找的是序列末尾最小的，则必有 $a\le b\le x$

因此我们可以交换贪心解法的x + seq1序列和最优解的x + seq2序列，将贪心解法调整成最优解方案，且并没有增加子序列个数。

因此，只要贪心解与最优解不同，我们就可以通过上述的调整，将贪心解调整成最优解，且没有增加序列的个数。贪心解 >= 最优解得证。

综上所述，贪心解 == 最优解

重要性质：

• 最长上升子序列问题和最少覆盖下降子序列问题是对偶问题
• Dilworth定理：偏序集能划分成的最少的全序集个数等于最大反链的元素个数。

程序代码

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

const int N = 1010;
int h[N], f[N], g[N];
int n;

int main()
{
    while( cin >> h[n] ) {
        n++;
    }
    // 第一问
    int res = 0;
    for(int i = 0; i < n; i++) {
        f[i] = 1;
        for(int j = 0; j < i; j++) {
            if(h[i] <= h[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;
        // 找到最小的那个g[k] >= h[i]
        while(k < cnt && g[k] < h[i])  k++;
        g[k] = h[i];
        if(k >= cnt)  cnt++;
    }
    cout << cnt << endl;
    return 0;
}

复杂度分析

时间复杂度为 $O(N^2)$

对于第二问，找所有大于等于g[k]中，最小的那个，可以使用二分查找来实现，将第二问的时间复杂度降到 $O(NlogN)$

导弹防御系统

题目描述

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。

第二行包含 n 个不同的整数，表示每个导弹的高度。

当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。

输出格式

对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

问题分析

本质上是求最少能覆盖整个序列的上升子序列 or 下降子序列个数【可以同时用上升序列和下降序列】。

对于这道题，没有很好的解法，只能通过暴力搜索，即考虑每个数是放在上升子序列或者下降子序列中，然后搜索全局最小值。

搜索过程中，可以判断当前子序列的个数是否超过了当前的最优解，若超过则进行剪枝操作，减小搜索空间。

这里搜索使用 DFS 实现。

程序代码

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

const int N = 55;

int n;
int q[N];
int up[N], down[N];  // 分别记录上升子序列和下降子序列
int ans;  // 全局最小值

// u：数的下标
// su：上升子序列个数
// sd：下降子序列个数
void dfs(int u, int su, int sd)
{
    // 剪枝
    if(su + sd >= ans)  return;
    // su + sd < ans
    if(u == n) {
        ans = su + sd;
        return ;
    }
    
    // 情况1：将当前数放入上升子序列
    int k = 0;
    while(k < su && up[k] >= q[u])  k++;
    // 记录，方便恢复现场
    int t = up[k];
    up[k] = q[u];
    if( k >= su) {
        dfs(u + 1, su + 1, sd);
    }
    else {
        dfs(u + 1, su, sd);
    }
    
    // 恢复现场
    up[k] = t;
    
    // 情况2：将当前数放入下降子序列
    k = 0;
    while(k < sd && down[k] <= q[u])  k++;
    t = down[k];
    down[k] = q[u];
    if(k >= sd) {
        dfs(u + 1, su, sd + 1);
    }
    else {
        dfs(u + 1, su, sd);
    }
    
    // 恢复现场
    down[k] = t;
}

int main()
{
    while(cin >> n, n) {
        for(int i = 0; i < n; i++) {
            cin >> q[i];
        }
        ans = n;
        dfs(0, 0, 0);
        
        cout << ans << endl;
    }
    return 0;
}