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

dp-拦截导弹2

所有代码均来自于acwing中的算法基础课和算法提高课
Description

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,
但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此
有可能不能拦截所有的导弹。

Input

第一行输入M表示包含M组测试数据,每组第一个输入N (N<100)表示后面有N个整数,表示导弹依次飞来的高度(雷达给出的高度数据是
不大于30000的正整数)。

Output

对于每组输入数据,第一行输出这套系统最多能拦截多少导弹,以及输出如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

Sample Input

2
7 300 250 275 252 200 138 245
7 181 205 471 782 1033 1058 1111

Sample Output

5 2
1 7

#include "iostream"
#include "cstring"using namespace std;
const int N = 110;
int a[N];
int g[N];  // 第i套系统末尾元素
int f[N];  // 以第i个元素结尾的最长非下降子序列的数量
int length;  // 目前需要的系统的数量int main() {int M;cin >> M;while (M--) {int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}// 求最长非下降子序列的数量for (int i = 1; i <=n ; ++i) {f[i]=1;for (int j = 1; j <i ; ++j) {if(a[i]<=a[j]){f[i] = max(f[i],f[j]+1);}}}int result = f[1];for (int i = 2; i <=n ; ++i) {result = max(result,f[i]);}cout << result<<" ";// 求所需要的系统的数量length = 1;for (int i = 1; i <= n; ++i) {int l = 1, r = length;while (l < r) {int mid = (l + r + 1) >> 1;if (a[i] <= g[mid]) {r = mid -1;} else {l = mid;}}g[r + 1] = a[i];length = max(length, r + 1);}cout << length-1 << endl;}
}

相关文章:

dp-拦截导弹2

所有代码均来自于acwing中的算法基础课和算法提高课 Description 某国为了防御敌国的导弹袭击&#xff0c;发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷&#xff1a;虽然它的第一发炮弹能够到达任意的高度&#xff0c; 但是以后每一发炮弹都不能高于前一发的高度。…...

初识动态规划算法(题目加解析)

文章目录 什么是动态规划正文力扣题第 N 个泰波那契数三步问题使用最小花费爬楼梯 总结 什么是动态规划 线性动态规划&#xff1a;是可以用一个dp表来存储内容&#xff0c;并且找到规律存储,按照规律存储。让第i个位置的值等于题目要求的答案 >dp表&#xff1a;dp表就是用一…...

Vue2.0与Vue3.0的区别

一、Vue2和Vue3的数据双向绑定原理发生了改变 Vue2的双向数据绑定是利用ES5的一个API&#xff0c;Object.definePropert()对数据进行劫持 结合 发布 订阅模式的方式来实现的。通过Object.defineProperty来劫持数据的setter&#xff0c;getter&#xff0c;在数据变动时发布消息…...

探索人工智能领域——每日20个名词详解【day6】

目录 前言 正文 总结 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高兴与大家相识&#xff0c;希望我的博客能对你有所帮助。 &#x1f4a1;本文由Filotimo__✍️原创&#xff0c;首发于CSDN&#x1f4da;。 &#x1f4e3;如需转载&#xff0c;请事先与我联系以…...

C++初阶 | [七] string类(上)

摘要&#xff1a;标准库中的string类的常用函数 C语言中&#xff0c;字符串是以\0结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列的库函数&#xff0c; 但是这些库函数与字符串是分离开的&#xff0c;不太符合OOP(面向对象)的思想&#…...

Django总结

文章目录 一、Web应用Web应用程序的优点Web应用程序的缺点应用程序有两种模式C/S、B/S C/S 客户端/服务端局域网连接其他电脑的MySQL数据库1.先用其他电脑再cmd命令行ping本机ip2.开放MySQL的访问 B/S 浏览器/服务端基于socket编写一个Web应用 二、Http协议1.http协议是什么2.h…...

【qml入门系列教程】:qml QtObject用法介绍

作者:令狐掌门 技术交流QQ群:675120140 博客地址:https://mingshiqiang.blog.csdn.net/ 文章目录 QtObject 是 Qt/QML 中的一个基础类型,通常用作创建一个没有 UI 的(不渲染任何东西的)纯逻辑对象。可以使用它来组织代码、存储状态或者作为属性和方法的容器。 以下是如何…...

2分图匹配算法

定义 节点u直接无边&#xff0c;v之间无边&#xff0c;边只存在uv之间。判断方法&#xff1a;BFS染色法&#xff0c;全部染色后&#xff0c;相邻边不同色 无权二部图中的最大匹配 最大匹配即每一个都匹配上min&#xff08;u&#xff0c; v&#xff09;。贪心算法可能导致&…...

[EndNote学习笔记] 导出库中文献的作者、标题、年份到Excel

菜单栏Edit中&#xff0c;选择 Output Styles 在默认的 Annotated上进行修改&#xff0c;在Bibliography栏下的Templates中修改想要导出的格式 其中&#xff0c;每个粗体标题表示&#xff0c;针对不同的文献类型&#xff0c;设置相应的导出格式。一般为Journal Article&…...

SQL Sever 基础知识 - 数据查询

SQL Sever 基础知识 - 一、查询数据 一、查询数据第1节 基本 SQL Server 语句SELECT第2节 SELECT语句示例2.1 SELECT - 检索表示例的某些列2.2 SELECT - 检索表的所有列2.3 SELECT - 对结果集进行筛选2.4 SELECT - 对结果集进行排序2.5 SELECT - 对结果集进行分组2.5 SELECT - …...

Vue入门——v-on标签

文章目录 规则v-on 一、案例总结 规则 v-on 作用&#xff1a;为html标签绑定事件语法&#xff1a; v-on&#xff1a;事件名&#xff1a;“函数名”简写为 事件名“函数名” 注意&#xff1a;函数需要定义在methods选项内部 一、案例 我们给案件绑定一个单击事件 <!DOCTYPE…...

JVM:双亲委派(未完结)

类加载 定义 一个java文件从编写代码到最终运行&#xff0c;必须要经历编译和类加载的过程&#xff0c;如下图&#xff08;图源自b站视频up主“跟着Mic学架构”&#xff09;。 编译就是把.java文件变成.class文件。类加载就是把.class文件加载到JVM内存中&#xff0c;得到一…...

Leetcode 2661. 找出叠涂元素

Leetcode 2661. 找出叠涂元素题目 给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1&#xff0c;m * n] 内的 所有 整数。从下标 0 开始遍历 arr 中的每个下标 i &#xff0c;并将包含整数 arr[i] 的 mat 单元格涂色。请你找出 a…...

vscode代码调试配置

C/C代码调试 点击 vscode左侧的 run and debug&#xff0c;新建launch.json 和 tasks.json&#xff0c;并进行配置如下 launch.json {// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more informati…...

PTA 7-225 sdut-C语言实验- 冒泡排序中数据交换的次数

听说过冒泡排序么&#xff1f;一种很暴力的排序方法。今天我们不希望你用它来排序&#xff0c;而是希望你能算出从小到大冒泡排序的过程中一共进行了多少次数据交换。 输入格式: 输入数据的第一行为一个正整数 T &#xff0c;表示有 T 组测试数据。 接下来T行&#xff0c;每行…...

新的 BLUFFS 攻击导致蓝牙连接不再私密

蓝牙是一种连接我们设备的低功耗无线技术&#xff0c;有一个新的漏洞需要解决。 中间的攻击者可以使用新的 BLUFFS 攻击轻松窥探您的通信。 法国研究中心 EURECOM 的研究员 Daniele Antonioli 演示了六种新颖的攻击&#xff0c;这些攻击被定义为 BLUFFS&#xff08;蓝牙转发和…...

安全测试之推荐工具(一)

文章目录 一、前言二、Web安全&#xff08;一&#xff09;AppScan&#xff08;推荐&#xff09;&#xff08;二&#xff09;AWVS&#xff08;推荐&#xff09;&#xff08;三&#xff09;Burp Suite&#xff08;推荐&#xff09;&#xff08;四&#xff09;OWASP ZAP 三、主机安…...

final关键字

修饰 类&#xff0c;属性&#xff0c;方法&#xff0c;局部变量&#xff08;包括方法参数&#xff09; 类似c语言的const 使用方式&#xff1a; 1 不希望类被继承 用final类&#xff08;类很重要&#xff0c;担心别人重写/修改&#xff09; 2 不希望某…...

WPF MVVM模式下如何将UI窗口变量传参到Viewmodel层

WPF MVVM模式下如何将UI窗口变量传参到Viewmodel层 UI层窗口定义 //窗口中绑定ViewModel<hc:GlowWindow.DataContext><viewmodel:MainWindowViewModel /></hc:GlowWindow.DataContext>//注册初始化事件<hc:Interaction.Triggers><hc:EventTrigger…...

条款22:将成员变量声明为private

1.前言 首先&#xff0c;我们应该利用反证法&#xff0c;看看为什么成员变量不该是public&#xff0c;然后再了解所有反对public成员变量的论点同样适用于protected成员变量。最后得出一个结论&#xff1a;成员变量应该是private。 2.为什么不用public 如果成员变量不是publ…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...