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…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
Python第七周作业
Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt,并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径,并创建logs目录(若不存在) 3.递归遍历目录data,输出所有.csv文件的路径…...
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑 在电子商务领域,转化率与网站性能是决定商业成败的核心指标。今天,我们将深入解析不同类型电商平台的转化率基准,探讨页面加载速度对用户行为的…...
