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…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...

day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
用递归算法解锁「子集」问题 —— LeetCode 78题解析
文章目录 一、题目介绍二、递归思路详解:从决策树开始理解三、解法一:二叉决策树 DFS四、解法二:组合式回溯写法(推荐)五、解法对比 递归算法是编程中一种非常强大且常见的思想,它能够优雅地解决很多复杂的…...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践
01技术背景与业务挑战 某短视频点播企业深耕国内用户市场,但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大,传统架构已较难满足当前企业发展的需求,企业面临着三重挑战: ① 业务:国内用户访问海外服…...
Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合
无论是python,或者java 的大型项目中,都会涉及到 自身平台微服务之间的相互调用,以及和第三发平台的 接口对接,那在python 中是怎么实现的呢? 在 Python Web 开发中,FastAPI 和 Django 是两个重要但定位不…...
Windows 下端口占用排查与释放全攻略
Windows 下端口占用排查与释放全攻略 在开发和运维过程中,经常会遇到端口被占用的问题(如 8080、3306 等常用端口)。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口,帮助你高效解决此类问题。 一、准…...