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 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度, 但是以后每一发炮弹都不能高于前一发的高度。…...
初识动态规划算法(题目加解析)
文章目录 什么是动态规划正文力扣题第 N 个泰波那契数三步问题使用最小花费爬楼梯 总结 什么是动态规划 线性动态规划:是可以用一个dp表来存储内容,并且找到规律存储,按照规律存储。让第i个位置的值等于题目要求的答案 >dp表:dp表就是用一…...
Vue2.0与Vue3.0的区别
一、Vue2和Vue3的数据双向绑定原理发生了改变 Vue2的双向数据绑定是利用ES5的一个API,Object.definePropert()对数据进行劫持 结合 发布 订阅模式的方式来实现的。通过Object.defineProperty来劫持数据的setter,getter,在数据变动时发布消息…...
探索人工智能领域——每日20个名词详解【day6】
目录 前言 正文 总结 🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创,首发于CSDN📚。 📣如需转载,请事先与我联系以…...
C++初阶 | [七] string类(上)
摘要:标准库中的string类的常用函数 C语言中,字符串是以\0结尾的一些字符的集合,为了操作方便,C标准库中提供了一些str系列的库函数, 但是这些库函数与字符串是分离开的,不太符合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直接无边,v之间无边,边只存在uv之间。判断方法:BFS染色法,全部染色后,相邻边不同色 无权二部图中的最大匹配 最大匹配即每一个都匹配上min(u, v)。贪心算法可能导致&…...
[EndNote学习笔记] 导出库中文献的作者、标题、年份到Excel
菜单栏Edit中,选择 Output Styles 在默认的 Annotated上进行修改,在Bibliography栏下的Templates中修改想要导出的格式 其中,每个粗体标题表示,针对不同的文献类型,设置相应的导出格式。一般为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 作用:为html标签绑定事件语法: v-on:事件名:“函数名”简写为 事件名“函数名” 注意:函数需要定义在methods选项内部 一、案例 我们给案件绑定一个单击事件 <!DOCTYPE…...
JVM:双亲委派(未完结)
类加载 定义 一个java文件从编写代码到最终运行,必须要经历编译和类加载的过程,如下图(图源自b站视频up主“跟着Mic学架构”)。 编译就是把.java文件变成.class文件。类加载就是把.class文件加载到JVM内存中,得到一…...
Leetcode 2661. 找出叠涂元素
Leetcode 2661. 找出叠涂元素题目 给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1,m * n] 内的 所有 整数。从下标 0 开始遍历 arr 中的每个下标 i ,并将包含整数 arr[i] 的 mat 单元格涂色。请你找出 a…...
vscode代码调试配置
C/C代码调试 点击 vscode左侧的 run and debug,新建launch.json 和 tasks.json,并进行配置如下 launch.json {// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more informati…...
PTA 7-225 sdut-C语言实验- 冒泡排序中数据交换的次数
听说过冒泡排序么?一种很暴力的排序方法。今天我们不希望你用它来排序,而是希望你能算出从小到大冒泡排序的过程中一共进行了多少次数据交换。 输入格式: 输入数据的第一行为一个正整数 T ,表示有 T 组测试数据。 接下来T行,每行…...
新的 BLUFFS 攻击导致蓝牙连接不再私密
蓝牙是一种连接我们设备的低功耗无线技术,有一个新的漏洞需要解决。 中间的攻击者可以使用新的 BLUFFS 攻击轻松窥探您的通信。 法国研究中心 EURECOM 的研究员 Daniele Antonioli 演示了六种新颖的攻击,这些攻击被定义为 BLUFFS(蓝牙转发和…...
安全测试之推荐工具(一)
文章目录 一、前言二、Web安全(一)AppScan(推荐)(二)AWVS(推荐)(三)Burp Suite(推荐)(四)OWASP ZAP 三、主机安…...
final关键字
修饰 类,属性,方法,局部变量(包括方法参数) 类似c语言的const 使用方式: 1 不希望类被继承 用final类(类很重要,担心别人重写/修改) 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.前言 首先,我们应该利用反证法,看看为什么成员变量不该是public,然后再了解所有反对public成员变量的论点同样适用于protected成员变量。最后得出一个结论:成员变量应该是private。 2.为什么不用public 如果成员变量不是publ…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
