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

这篇具有很好参考价值的文章主要介绍了动态规划系列 | 最长上升子序列模型(下)| 拦截导弹一网打尽!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

拦截导弹

题目描述

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

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

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

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

输入导弹依次飞来的高度(雷达给出的高度数据是不大于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 实现。文章来源地址https://www.toymoban.com/news/detail-769231.html

程序代码

#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;
}

到了这里,关于动态规划系列 | 最长上升子序列模型(下)| 拦截导弹一网打尽!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划__最长上升子序列

    目录 一.最长上升子序列 最长上升子序列模板 O(n ^ 2) 最长上升子序列二分优化 O(nlongn) 1017. 怪盗基德的滑翔翼 1014. 登山 1012. 友好城市 1016. 最大上升子序列和 1010. 拦截导弹 187. 导弹防御系统 二.最长公共上升子序列 最长公共子序列 最长公共上升子序列 给定一个长度为 N 的数

    2024年02月04日
    浏览(41)
  • C++动态规划之最长上升子序列

    一个序列A={a1,a2,...an}中任意删除若干项,剩余的序列叫做A的一个子序列。例如序列A={1,3,5,4,2},删除其中的第3项和第5项,得到序列B={1,3,4},删除其中的第3项和第4项,得到序列C={1,3,2},此时序列B和C是序列A的子序列。 如果序列中的元素是从小到大排列的,则该序列为上升

    2023年04月14日
    浏览(43)
  • 最长上升子序列模型(LIS)

    最长上升子序列模型就像它的名字一样,用来从区间中找出最长上升的子序列。它主要用来处理区间中的挑选问题,可以处理上升序列也可以处理下降序列,原序列本身的顺序并不重要。 895. 最长上升子序列(活动 - AcWing) 896. 最长上升子序列 II(活动 - AcWing) 我们就这两个

    2024年01月19日
    浏览(40)
  • C++---最长上升子序列模型---最大上升子序列和(每日一道算法2023.3.3)

    注意事项: 本题为\\\"线性dp—最长上升子序列的长度\\\"的扩展题,所以dp思路这里就不再赘述。 题目: 比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等。 这些子序列中和最大为18,为子序列(1,3,5,9)的和。 你的任务,就是对于给定的序列,求出最大上升子序

    2024年02月03日
    浏览(37)
  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)

    力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出

    2024年02月01日
    浏览(55)
  • 两个数组的动态规划——最长公共子序列模型

    1.考虑空串,即dp表多出一行一列, 代表某个字符串为空。 2.考虑最后一个位置;是否相等; 3.可在字符串最前面加虚拟位置以对应映射关系; 4.一般横行是j,列是i。此时第一行代表第二个字符串不为空,即第一个字符串是空的 给你两个字符串  s   和  t  ,统计并返回在

    2024年03月10日
    浏览(65)
  • 上升子序列的最大长度,递归-记忆化搜索-动态规划三步走

    题目描述: 小明有一个数组,他想从数组任意元素开始向后遍历,找出所有上升子序列,并计算出最长的上升子序列的长度。 数据范围: 每组数据长度满足 1≤n≤200 1≤n≤200 , 数据大小满足 1≤val≤350 1≤val≤350 输入描述: 数据共2行,第1行先输入数组的个数,第2行再输

    2024年04月22日
    浏览(41)
  • 最长上升子序列问题(LIS问题)与最长不上升子序列问题的四种方法(c++ 模板代码)

    最大上升子序列问题也叫做LIS问题,与最大公共子序列LCS问题是一类经典问题,在本章我们将总结一下求解 LIS最大上升子序列 的 几种方法 ,同时也会给出对应的 最大不上升子序列的求解方法。 关于LCS问题,我在后面会再出一篇博客来讲解, 废话不多说,我们直接进入正题

    2024年02月03日
    浏览(43)
  • 最长公共上升子序列(LCIS)

    目录 一、前言 二、最长公共上升子序列 1、问题描述 2、基本思路 (1)状态表示 (2)状态计算 三、题例 1、上链接 2、基本思路 3、代码 (1)python未优化版 (2)python优化版 对于学计算机的同学来说,学习算法是一件非常重要的事情,废话不多讲,我们来讲讲“最长公共上

    2023年04月09日
    浏览(33)
  • [ACM 学习] 最长上升子序列

    LIS(最长上升子序列)的三种经典求法 - 一只不咕鸟 - 博客园 (cnblogs.com) 理解一下第三种方法(贪心+二分查找) 因为构建的是上升子序列,所以是可以用二分查找找到最大的小于当前 A[i] 的在子序列中的 F[j],并更新 F[j+1] 注:刚开始看的时候还在疑惑只换一个的话,后面的

    2024年01月16日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包