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

【算法】拦截导弹(线性DP)

题目 

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

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

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

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

输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

共一行,输入导弹依次飞来的高度。

输出格式

第一行包含一个整数,表示最多能拦截的导弹数。

第二行包含一个整数,表示要拦截所有导弹最少要配备的系统数。

数据范围

雷达给出的高度数据是不大于 30000 的正整数,导弹数不超过 1000。

输入样例:

389 207 155 300 299 170 158 65

输出样例:

6
2

思路

求一台设备拦截的最大数量:求最大非上升子序列。

求需要多少设备才能全部拦截:

开一个数组p[],初始状态为空,cnt代表设备数,p[i]代表第i台设备所能拦截的最大高度。

当我们遇到一枚导弹时我们有两个选择:

1、使用现有设备进行拦截

2、新增加一台设备进行拦截

如果中间状态如下:(可以确保q[]数组是递增的,因为无法拦截的导弹会放入当前最后的一个位置)

当高度为2的导弹来袭的时候,优先使用p[0] = 3进行拦截,然后p[0] = 2;

【2,5,7】

当高度为5的导弹来袭的时候,优先使用p[1] = 5进行拦截,然后p[1] = 5;

【2,5,7】

当高度为8的导弹来袭的时候,现有设备无法拦截,新增加一个设备p[3],令p[3] = 8;

【2,5,7,8】 

当高度为4的导弹来袭的时候,优先使用p[1] = 5拦截,p[1] = 4;

【2,4,7,8】

代码 

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n;
int h[N],f[N],q[N];int main()
{string s;getline(cin,s);stringstream ssin(s);while(ssin >> h[n]) n ++;int res = 0,cnt = 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]);int k = 0;while(k < cnt && h[i] > q[k]) k ++;if(k == cnt){q[cnt] = h[i];cnt ++;}else{q[k] = h[i];}}cout << res << endl << cnt << endl;return 0;
}

题目来自:1010. 拦截导弹 - AcWing题库

相关文章:

【算法】拦截导弹(线性DP)

题目 某国为了防御敌国的导弹袭击&#xff0c;发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷&#xff1a;虽然它的第一发炮弹能够到达任意的高度&#xff0c;但是以后每一发炮弹都不能高于前一发的高度。 某天&#xff0c;雷达捕捉到敌国的导弹来袭。 由于该系…...

记 doris 加载压缩文件(lzo、snappy)pr

做了一个case&#xff0c;是doris支持加载lzo压缩文件。[improvement](load) Enable lzo & Remove dependency on Markus F.X.J. Oberhumers lzo library by HowardQin Pull Request #30573 apache/doris (github.com) 其实doris里已经支持了 lzo&#xff0c;这个case源…...

【Leetcode】2670. 找出不同元素数目差数组

文章目录 题目思路代码结果 题目 题目链接 给你一个下标从 0 开始的数组 nums &#xff0c;数组长度为 n 。 nums 的 不同元素数目差 数组可以用一个长度为 n 的数组 diff 表示&#xff0c;其中 diff[i] 等于前缀 nums[0, …, i] 中不同元素的数目 减去 后缀 nums[i 1, …, …...

༺༽༾ཊ—Unity之-01-工厂方法模式—ཏ༿༼༻

首先创建一个项目&#xff0c; 在这个初始界面我们需要做一些准备工作&#xff0c; 建基础通用文件夹&#xff0c; 创建一个Plane 重置后 缩放100倍 加一个颜色&#xff0c; 任务&#xff1a;使用工厂方法模式 创建 飞船模型&#xff0c; 首先资源商店下载飞船模型&#xff0c…...

QT仪表盘小工具

头文件: /**************************************************************************** ** ** Copyright (C) 2016 The Qt Company Ltd. ** Contact: https://www.qt.io/licensing/ ** ** This file is part of the examples of the Qt Toolkit. ** ** $QT_BEGIN_LICENSE…...

【2024】大三寒假再回首:缺乏自我意识是毒药,反思和回顾是解药

2024年初&#xff0c;学习状态回顾 开稿时间&#xff1a;2024-1-23 归家百里去&#xff0c;飘雪送客迟。 搁笔日又久&#xff0c;一顾迷惘时。 我们饱含着过去的习惯&#xff0c;缺乏自我意识是毒药&#xff0c;反思和回顾是解药。 文章目录 2024年初&#xff0c;学习状态回顾一…...

计算机网络——网络层(3)

计算机网络——网络层&#xff08;3&#xff09; 小程一言专栏链接: [link](http://t.csdnimg.cn/ZUTXU)1 网络层——控制平面因特网中自治系统内部的路由选择总括考虑因素总结 ISP之间的路由选择&#xff1a;BGP考虑因素总结 SDN控制层面重要组件和功能总结 ICMP主要功能和特点…...

ROS2 学习笔记12:使用 colcon 构建软件包

ROS2 学习笔记12&#xff1a;使用 colcon 构建软件包 Background 背景Prerequisites 前提1 Install colcon2 Install ROS 2 Basics 基础1 Create a workspace2 Add some sources3 Source an underlay4 Build the workspace5 Run tests6 Source the environment7 Try a demo Cre…...

基于JAVA+SpringBoot+Vue的前后端分离的医院管理系统

✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取项目下载方式&#x1f345; 一、项目背景介绍&#xff1a; 随着计算机科学的迅猛…...

npm淘宝镜像过期解决办法

npm淘宝镜像过期解决办法 因为npm 官方镜像&#xff08;registry.npmjs.org&#xff09;在国内访问很慢&#xff0c;我们基本上都会选择切换到国内的一些 npm 镜像&#xff08;淘宝镜像、腾讯云镜像等&#xff09;。由于淘宝原来的镜像&#xff08;registry.npm.taobao.org&am…...

Arduino 官网上下载和使用开发板

在 Arduino 官网上下载和使用开发板可以按照以下步骤进行&#xff1a; 打开浏览器&#xff0c;访问 Arduino 官网&#xff08;https://www.arduino.cc/&#xff09;。在官网首页&#xff0c;可以看到各种型号的 Arduino 开发板和相关产品。根据自己的需求选 择合适的开发板型号…...

k8s学习-DaemonSet和Job

1.1DaemonSet是什么 Deployment部署的副本Pod会分布在各个Node上&#xff0c;每个Node都可能运行好几个副本。DaemonSet的不同之处在于&#xff1a;每个Node上最多只能运行⼀个副本。DaemonSet的典型应用场景有&#xff1a; &#xff08;1&#xff09;在集群的每个节点上运⾏存…...

【开源】SpringBoot框架开发海南旅游景点推荐系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 用户端2.2 管理员端 三、系统展示四、核心代码4.1 随机景点推荐4.2 景点评价4.3 协同推荐算法4.4 网站登录4.5 查询景点美食 五、免责说明 一、摘要 1.1 项目介绍 基于VueSpringBootMySQL的海南旅游推荐系统&#xff…...

Windows10更新失败 错误 0x80070643、KB5034441的解决方法之二

Windows10更新失败 错误 0x80070643、KB5034441 在知乎Windows10更新失败 错误 0x80070643、KB5034441的原因分析和几个解决方法 - 知乎 参考文章进行操作&#xff0c;更详细信息自己看上面链接。 我电脑的硬盘是mbr格式&#xff0c;而且没有划分恢复分区。 Microsoft Windo…...

SQL中LIMIT的简单用法

在SQL的世界里&#xff0c;有一位神秘而强大的限制者&#xff0c;它就是 LIMIT。今天&#xff0c;我们将深入探讨这个神秘的SQL关键字&#xff0c;揭开它的神秘面纱&#xff0c;让你能够更好地使用它来操控你的数据。 背景 首先&#xff0c;让我们了解一下为什么我们需要 LIM…...

canvas自定义扩展方法:文字自动换行

查看专栏目录 canvas实例应用100专栏&#xff0c;提供canvas的基础知识&#xff0c;高级动画&#xff0c;相关应用扩展等信息。canvas作为html的一部分&#xff0c;是图像图标地图可视化的一个重要的基础&#xff0c;学好了canvas&#xff0c;在其他的一些应用上将会起到非常重…...

【2024全网最详细】Google 搜索命令终极指南

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 你是否尝试过使用 Google 搜索作为免费的 SEO …...

R-kknn包-类别插值可视化绘制

前面的推文我们介绍了使用scikit-learn结合分类散点数据&#xff0c;构建机器学习分类模型并将模型结果可视化展示&#xff0c;具体链接如下&#xff1a; 机器学习和可视化还能一起这样用&#xff1f;Python教你全搞定。今天这篇推文&#xff0c;我们就使用R语言的kknn包进行类…...

探究HMAC算法:消息认证与数据完整性的完美结合

Hash-based Message Authentication Code&#xff08;基于哈希的消息认证码&#xff0c;简称HMAC&#xff09;算法作为一种广泛应用的消息认证码&#xff08;MAC&#xff09;算法&#xff0c;在现代信息安全领域起着至关重要的作用。本文将从算法原理、优缺点、实际应用等方面&…...

10s 内得到一个干净、开箱即用的 Linux 系统

安装 使用官方脚本安装我的服务器不行 官方脚本 mkdir instantbox && cd $_ bash <(curl -sSL https://raw.githubusercontent.com/instantbox/instantbox/master/init.sh) 下面是我的完整安装过程 mkdir /opt/instantbox cd /opt/instantbox 1.脚本文件 (这个没…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...