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

发布时间:2023年12月25日

拦截导弹

题目描述

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

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

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

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

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

输入格式

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

输出格式

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

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

问题分析

第一问

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

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

第二问

采用贪心的策略:

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

贪心正确性证明

证明:贪心解 >= 最优解

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

证明:贪心解 <= 最优解

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

在这里插入图片描述

由于贪心法找的是序列末尾最小的,则必有 a ≤ b ≤ x a \leq b \leq x abx

因此我们可以交换贪心解法的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 ) O(N^2) O(N2)

对于第二问,找所有大于等于g[k]中,最小的那个,可以使用二分查找来实现,将第二问的时间复杂度降到 O ( N l o g N ) O(NlogN) 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;
}
文章来源:https://blog.csdn.net/qq_45931691/article/details/135202000
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。