C++---最长上升子序列模型---拦截导弹(每日一道算法2023.3.4)
注意事项:
本题为"线性dp—最长上升子序列的长度"的扩展题,这里只讲贪心思路,dp去这个看。
题目:
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。
某天,雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行,输入导弹依次飞来的高度。
输出格式
第一行包含一个整数,表示最多能拦截的导弹数。
第二行包含一个整数,表示要拦截所有导弹最少要配备的系统数。
数据范围
雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000。
输入:
389 207 155 300 299 170 158 65
输出:
6
2
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010;
int n;
int w[N], f[N], g[N];//最长下降子序列模板
int lis() {int res = 0;for (int i = 0; i<n; i++) {f[i] = 1;for (int j = 0; j<i; j++) {if (w[j] >= w[i]) f[i] = max(f[i], f[j] + 1); //这里注意是>=,因为题目中说的是每一发炮弹都不能高于前一发的高度。}res = max(res, f[i]);}return res;
}int main()
{//读入int x;while (cin >> x) w[n++] = x;//dp最长下降子序列模板cout << lis() << endl;//贪心求出最多需要多少个策略, res表示链的个数。//思路是每次从第一个链开始,找到比当前值大,且在是所有链尾中最小的那个,将其替换,也就是单调下降队列的思路。//如何证明这样写,就一定保证w[i]会加在比当前导弹大且在所有链尾中最小的后面?//假设有两条链, g[1]=...x1, g[2]=...x2, 那么此时x1必定小于x2, 因为如果x2<x1, 那么g[1]应该=...x1x2。int res = 0;for (int i = 0; i<n; i++) {int k = 0;while (k < res && g[k] < w[i]) k++;g[k] = w[i];if (k >= res) res++;}cout << res << endl;return 0;
}
思路:
dp思路和最长上升子序列长度一样,不多讲。
这里着重说一下第二部分的贪心的思路。
首先猜测一下性质,根据题目所说,需要求出几套系统能够拦截所有导弹。
那也就是找到,用几个下降子序列能够完全覆盖整个数列。
可以将每个下降子序列看作一个链,完全单调下降,每遇到一个新的导弹,尝试将其放到合适的下降子序列的末尾,那怎么算是合适呢?
答案是找到当前所有链尾中,比新导弹高度更高,且是所有链尾中最小的那个。
怎么证明这个贪心思路是正确的:调整法
首先贪心答案(A), 最优解(B), 证明A >= B, B >= A,也就是A = B
A >= B:
因为贪心是一种解,所以符合A >= B.
B >= A:
当条件成立,而A != B, 说明A和B肯定有某个链是不同的,也就是在链的某个点c产生了分歧:
贪心:a1链…c…
最优:a2链…c…
而贪心的策略是将每个数放到比新导弹大,且是链尾中最小的那个后面,那就说明最优解的前一个量,是要比贪心解的前一个量要大的,那么就可以将贪心解的c替换到最优解的c的位置,而不影响链的数量,即证明了A = B
声明:
算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流
相关文章:
C++---最长上升子序列模型---拦截导弹(每日一道算法2023.3.4)
注意事项: 本题为"线性dp—最长上升子序列的长度"的扩展题,这里只讲贪心思路,dp去这个看。 题目: 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷:虽然它…...
【机器学习面试】百面机器学习笔记和问题总结+扩展面试题
第1章 特征工程 1、为什么需要对数值类型的特征做归一化? (1)消除量纲,将所有特征统一到一个大致相同的区间范围,使不同指标之间具由可比性; (2)可以加快梯度下降收敛的速度&#…...
【2021.12.28】ctf逆向中的迷宫问题(含exe及wp)
【2021.12.28】ctf逆向中的迷宫问题(含exe及wp) 文章目录【2021.12.28】ctf逆向中的迷宫问题(含exe及wp)1、迷宫简介(1)简单例子(2)一般的迷宫代码2、二维迷宫(1…...
WSL2使用Nvidia-Docker实现深度学习环境自由部署
1. Win11 显卡驱动的安装 注意:WSL2中是不需要且不能安装任何显卡驱动的,它的显卡驱动完全依赖于 Win11 中的显卡驱动,因此我们只需要安装你显卡对应的 Win11 版本显卡驱动版本(必须是 Win11 版本的驱动),…...
SpringBoot入门 - 配置热部署devtools工具
在SpringBoot开发调试中,如果我每行代码的修改都需要重启启动再调试,可能比较费时间;SpringBoot团队针对此问题提供了spring-boot-devtools(简称devtools)插件,它试图提升开发调试的效率。准备知识点什么是…...
CANFDNET-200U-UDP配置与数据收发控制
一、启动ZCANPRP,打开设备管理页面,选择类型CANFDNET-200U-UDP,如图1 图1 二、打开设备,启动,在相应页面如图2,配置协议,CANFD 加速,本地端口,IP地址,工作端口。 图2 三、发送相应数…...
嵌入式中backtrace的使用
大家好,我是bug菌~ backtrace主要用于调试程序时,能够打印出程序在运行过程中的函数调用栈,以帮助开发者快速定位程序出现异常或崩溃的原因。 通过backtrace的输出,开发者可以了解程序在哪个函数出现问题,…...
CV学习笔记-Faster-RCNN
Faster R-CNN 文章目录Faster R-CNN1. 目标检测算法1.1 计算机视觉有五大应用1.2 目标检测任务1.3 目标检测算法概述2. 边框回归(Bounding-Box regression)2.1 IoU2.2 统计学中的指标2.3 边框回归3. Faster-RCNN网络3.1 Conv layers3.2 Region Proposal …...
大型三甲医院云HIS系统源码 强大的电子病历+完整文档
医院HIS系统源码云HIS系统:SaaS运维平台多医院入驻强大的电子病历完整文档 有源码,有演示 一、系统概述 采用主流成熟技术,软件结构简洁、代码规范易阅读,SaaS应用,全浏览器访问前后端分离,多服务协同&am…...
如何使用Spring Cloud搭建高可用的Elasticsearch集群?详解Elasticsearch的安装与配置及Spring Boot集成的实现
Spring Cloud 是一个基于 Spring Boot 的微服务框架,它提供了一系列组件和工具,方便开发人员快速搭建和管理分布式系统。Elasticsearch 是一个开源的全文搜索引擎,也是一个分布式、高可用的 NoSQL 数据库。本篇博客将详细讲解如何使用 Spring…...
phpinfo包含临时文件Getshell全过程及源码
目录 前言 原理 漏洞复现 靶场环境 源码 复现过程 前言 PHP LFI本地文件包含漏洞主要是包含本地服务器上存储的一些文件,例如session文件、日志文件、临时文件等。但是,只有我们能够控制包含的文件存储我们的恶意代码才能拿到服务器权限。假如在服…...
ubuntu22.04 Desktop 服务器安装
操作系统 使用的是Uubntu22.04 Desktop的版本,系统安装后,默认开启了53端口和631端口 关闭udp 5353、53791端口(avahi-daemon服务) sudo systemctl stop avahi-daemon.socket avahi-daemon.service sudo systemctl disable ava…...
Halcon——关于halcon中的一些语法
Halcon——关于halcon中的一些语法前言一、变量的创建与赋值二、if语句三、for语句四、while语句五、中断语句六、switch语句总结前言 在HDevelep环境下编程时,所用的一些语法与C#有些差异,在此做下记录。 一、变量的创建与赋值 Hdevelep中调用函数时&…...
Java 循环语句
Java 循环语句 循环语句就是在满足一定条件的情况下反复执行某一个操作的语句。Java中提供了3种常用的循环语句,分别是while循环语句、do…while循环语句和for循环语句。 1.while循环语句 while语句也称条件判断语句,它的循环方式为利用一个条件来控制…...
Python 基础语法
文章目录条件判断循环数据类型变量字符编码字符串格式化listtupledictset不可变对象”#“ 开头的是注释每一行是一个语句,当语句以冒号 “:” 结尾时,缩进的语句被视为代码块 好处:强迫代码格式化,强迫少用缩进 坏处:“…...
Kubernetes:通过 kubectl 插件 ketall 查看所有APi对象资源
写在前面 分享一个查看集群所有资源的小工具博文内容涉及: 下载安装常用命令 Demo 理解不足小伙伴帮忙指正 出其东门,有女如云。虽则如云,匪我思存。缟衣綦巾,聊乐我员。——《郑风出其东门》 分享一个查看集群所有资源的小工具&a…...
Zookeeper3.5.7版本——选举机制(非第一次启动)
目录一、ZooKeeper集群中哪些情况会进入Leader选举二、当一台机器进入Leader选举流程时,当前集群的两种状态2.1、集群中本来就已经存在一个Leader2.2、集群中确实不存在Leader三、Zookeeper中的一些概念了解3.1、SID3.2、ZXID3.3、Epoch一、ZooKeeper集群中哪些情况…...
Python | Leetcode刷题日寄Part05
欢迎交流学习~~ LeetCode & Python 系列: 🏆 Python | Leetcode刷题日寄Part01 🔎 Python | Leetcode刷题日寄Part02 💝 Python | Leetcode刷题日寄Part03 ✈️ Python | Leetcode刷题日寄Part04 Python|Leetcode刷题日寄Par…...
SpringCloud学习笔记(一)
单体应用架构 在诞⽣之初,拉勾的⽤户量、数据量规模都⽐较⼩,项目所有的功能模块都放在一个工程中编码、编译、打包并且部署在一个Tomcat容器中的架构模式就是单体应用架构。 优点: 高效开发:项⽬前期开发节奏快,团…...
【C语言指针练习题】你真的学会指针了吗?
✨✨✨✨如果文章对你有帮助记得点赞收藏关注哦!!✨✨✨✨ 文章目录✨✨✨✨如果文章对你有帮助记得点赞收藏关注哦!!✨✨✨✨一维数组练习题:字符数组练习题:字符指针练习题:二维数组练习题&am…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
