当前位置: 首页 > news >正文

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)

注意事项&#xff1a; 本题为"线性dp—最长上升子序列的长度"的扩展题&#xff0c;这里只讲贪心思路&#xff0c;dp去这个看。 题目&#xff1a; 某国为了防御敌国的导弹袭击&#xff0c;发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷&#xff1a;虽然它…...

【机器学习面试】百面机器学习笔记和问题总结+扩展面试题

第1章 特征工程 1、为什么需要对数值类型的特征做归一化&#xff1f; &#xff08;1&#xff09;消除量纲&#xff0c;将所有特征统一到一个大致相同的区间范围&#xff0c;使不同指标之间具由可比性&#xff1b; &#xff08;2&#xff09;可以加快梯度下降收敛的速度&#…...

【2021.12.28】ctf逆向中的迷宫问题(含exe及wp)

【2021.12.28】ctf逆向中的迷宫问题&#xff08;含exe及wp&#xff09; 文章目录【2021.12.28】ctf逆向中的迷宫问题&#xff08;含exe及wp&#xff09;1、迷宫简介&#xff08;1&#xff09;简单例子&#xff08;2&#xff09;一般的迷宫代码2、二维迷宫&#xff08;1&#xf…...

WSL2使用Nvidia-Docker实现深度学习环境自由部署

1. Win11 显卡驱动的安装 注意&#xff1a;WSL2中是不需要且不能安装任何显卡驱动的&#xff0c;它的显卡驱动完全依赖于 Win11 中的显卡驱动&#xff0c;因此我们只需要安装你显卡对应的 Win11 版本显卡驱动版本&#xff08;必须是 Win11 版本的驱动&#xff09;&#xff0c;…...

SpringBoot入门 - 配置热部署devtools工具

在SpringBoot开发调试中&#xff0c;如果我每行代码的修改都需要重启启动再调试&#xff0c;可能比较费时间&#xff1b;SpringBoot团队针对此问题提供了spring-boot-devtools&#xff08;简称devtools&#xff09;插件&#xff0c;它试图提升开发调试的效率。准备知识点什么是…...

CANFDNET-200U-UDP配置与数据收发控制

一、启动ZCANPRP,打开设备管理页面&#xff0c;选择类型CANFDNET-200U-UDP,如图1 图1 二、打开设备&#xff0c;启动&#xff0c;在相应页面如图2&#xff0c;配置协议&#xff0c;CANFD 加速&#xff0c;本地端口&#xff0c;IP地址&#xff0c;工作端口。 图2 三、发送相应数…...

嵌入式中backtrace的使用

大家好&#xff0c;我是bug菌&#xff5e; backtrace主要用于调试程序时&#xff0c;能够打印出程序在运行过程中的函数调用栈&#xff0c;以帮助开发者快速定位程序出现异常或崩溃的原因。 通过backtrace的输出&#xff0c;开发者可以了解程序在哪个函数出现问题&#xff0c…...

CV学习笔记-Faster-RCNN

Faster R-CNN 文章目录Faster R-CNN1. 目标检测算法1.1 计算机视觉有五大应用1.2 目标检测任务1.3 目标检测算法概述2. 边框回归&#xff08;Bounding-Box regression&#xff09;2.1 IoU2.2 统计学中的指标2.3 边框回归3. Faster-RCNN网络3.1 Conv layers3.2 Region Proposal …...

大型三甲医院云HIS系统源码 强大的电子病历+完整文档

医院HIS系统源码云HIS系统&#xff1a;SaaS运维平台多医院入驻强大的电子病历完整文档 有源码&#xff0c;有演示 一、系统概述 采用主流成熟技术&#xff0c;软件结构简洁、代码规范易阅读&#xff0c;SaaS应用&#xff0c;全浏览器访问前后端分离&#xff0c;多服务协同&am…...

如何使用Spring Cloud搭建高可用的Elasticsearch集群?详解Elasticsearch的安装与配置及Spring Boot集成的实现

Spring Cloud 是一个基于 Spring Boot 的微服务框架&#xff0c;它提供了一系列组件和工具&#xff0c;方便开发人员快速搭建和管理分布式系统。Elasticsearch 是一个开源的全文搜索引擎&#xff0c;也是一个分布式、高可用的 NoSQL 数据库。本篇博客将详细讲解如何使用 Spring…...

phpinfo包含临时文件Getshell全过程及源码

目录 前言 原理 漏洞复现 靶场环境 源码 复现过程 前言 PHP LFI本地文件包含漏洞主要是包含本地服务器上存储的一些文件&#xff0c;例如session文件、日志文件、临时文件等。但是&#xff0c;只有我们能够控制包含的文件存储我们的恶意代码才能拿到服务器权限。假如在服…...

ubuntu22.04 Desktop 服务器安装

操作系统 使用的是Uubntu22.04 Desktop的版本&#xff0c;系统安装后&#xff0c;默认开启了53端口和631端口 关闭udp 5353、53791端口&#xff08;avahi-daemon服务&#xff09; sudo systemctl stop avahi-daemon.socket avahi-daemon.service sudo systemctl disable ava…...

Halcon——关于halcon中的一些语法

Halcon——关于halcon中的一些语法前言一、变量的创建与赋值二、if语句三、for语句四、while语句五、中断语句六、switch语句总结前言 在HDevelep环境下编程时&#xff0c;所用的一些语法与C#有些差异&#xff0c;在此做下记录。 一、变量的创建与赋值 Hdevelep中调用函数时&…...

Java 循环语句

Java 循环语句 循环语句就是在满足一定条件的情况下反复执行某一个操作的语句。Java中提供了3种常用的循环语句&#xff0c;分别是while循环语句、do…while循环语句和for循环语句。 1.while循环语句 while语句也称条件判断语句&#xff0c;它的循环方式为利用一个条件来控制…...

Python 基础语法

文章目录条件判断循环数据类型变量字符编码字符串格式化listtupledictset不可变对象”#“ 开头的是注释每一行是一个语句&#xff0c;当语句以冒号 “:” 结尾时&#xff0c;缩进的语句被视为代码块 好处&#xff1a;强迫代码格式化&#xff0c;强迫少用缩进 坏处&#xff1a;“…...

Kubernetes:通过 kubectl 插件 ketall 查看所有APi对象资源

写在前面 分享一个查看集群所有资源的小工具博文内容涉及&#xff1a; 下载安装常用命令 Demo 理解不足小伙伴帮忙指正 出其东门&#xff0c;有女如云。虽则如云&#xff0c;匪我思存。缟衣綦巾&#xff0c;聊乐我员。——《郑风出其东门》 分享一个查看集群所有资源的小工具&a…...

Zookeeper3.5.7版本——选举机制(非第一次启动)

目录一、ZooKeeper集群中哪些情况会进入Leader选举二、当一台机器进入Leader选举流程时&#xff0c;当前集群的两种状态2.1、集群中本来就已经存在一个Leader2.2、集群中确实不存在Leader三、Zookeeper中的一些概念了解3.1、SID3.2、ZXID3.3、Epoch一、ZooKeeper集群中哪些情况…...

Python | Leetcode刷题日寄Part05

欢迎交流学习~~ LeetCode & Python 系列&#xff1a; &#x1f3c6; Python | Leetcode刷题日寄Part01 &#x1f50e; Python | Leetcode刷题日寄Part02 &#x1f49d; Python | Leetcode刷题日寄Part03 ✈️ Python | Leetcode刷题日寄Part04 Python|Leetcode刷题日寄Par…...

SpringCloud学习笔记(一)

单体应用架构 在诞⽣之初&#xff0c;拉勾的⽤户量、数据量规模都⽐较⼩&#xff0c;项目所有的功能模块都放在一个工程中编码、编译、打包并且部署在一个Tomcat容器中的架构模式就是单体应用架构。 优点&#xff1a; 高效开发&#xff1a;项⽬前期开发节奏快&#xff0c;团…...

【C语言指针练习题】你真的学会指针了吗?

✨✨✨✨如果文章对你有帮助记得点赞收藏关注哦&#xff01;&#xff01;✨✨✨✨ 文章目录✨✨✨✨如果文章对你有帮助记得点赞收藏关注哦&#xff01;&#xff01;✨✨✨✨一维数组练习题&#xff1a;字符数组练习题&#xff1a;字符指针练习题&#xff1a;二维数组练习题&am…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...