C++---最长上升子序列模型---怪盗基德的滑翔翼(每日一道算法2023.2.27)
注意事项:
本题为"线性dp—最长上升子序列的长度"的扩展题,所以dp思路这里就不再赘述。
题目:
怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。
而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪装,而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。
不得已,怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线,每幢建筑的高度各不相同。
初始时,怪盗基德可以在任何一幢建筑的顶端。
他可以选择一个方向逃跑,但是不能中途改变方向(因为中森警部会在后面追击)。
因为滑翔翼动力装置受损,他只能往下滑行(即:只能从较高的建筑滑翔到较低的建筑)。
他希望尽可能多地经过不同建筑的顶部,这样可以减缓下降时的冲击力,减少受伤的可能性。
请问,他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)?
输入格式
输入数据第一行是一个整数K,代表有K组测试数据。
每组测试数据包含两行:第一行是一个整数N,代表有N幢建筑。第二行包含N个不同的整数,每一个对应一幢建筑的高度h,按照建筑的排列顺序给出。
输出格式
对于每一组测试数据,输出一行,包含一个整数,代表怪盗基德最多可以经过的建筑数量。
数据范围
1≤K≤100,
1≤N≤100,
0<h<10000
输入:
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10
输出:
6
6
9
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 110;
int w[N], f[N];
int k, n; //接收k组数据,n每次会被更新// 最长上升子序列的基础模板
int lis() {for (int i = 1; i<= n; i++) {f[i] = 1;for (int j = 1; j<i; j++) {if (w[j] < w[i]) {f[i] = max(f[i], f[j]+1);}}}int res = 0;for (int i = 1; i<=n; i++) res = max(res, f[i]);return res;
}int main ()
{cin >> k;while (k--) { //k组数据cin >> n;for (int i = 1; i<=n; i++) cin >> w[i];//求一次最长上升子序列,然后把序列倒过来,再求一遍,相当于拿到最长下降子序列//也就是超两个方向飞都计算了,然后取最大值即可int m1 = lis();reverse(w+1, w+n+1); //这里记得从下标1开始翻转,因为读入是从1开始int m2 = lis();cout << max(m1, m2) << endl;}return 0;
}
思路:
根据题目中我们可以知道,需要选择向左或向右方向飞行,
那其实也就是要我们求出 最长上升子序列 和 最长下降子序列 的长度,取max即可,思路比较简单。
声明:
算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流
相关文章:
C++---最长上升子序列模型---怪盗基德的滑翔翼(每日一道算法2023.2.27)
注意事项: 本题为"线性dp—最长上升子序列的长度"的扩展题,所以dp思路这里就不再赘述。 题目: 怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。 而他最为突出的地方,就是他每次都能逃脱中…...

Python 之 Pandas 文件操作和读取 CSV 参数详解
文章目录一、Pandas 读取文件二、CSV 文件读取1. 基本参数2. 通用解析参数3. 空值处理相关参数4. 时间处理相关参数5. 分块读入相关参数一、Pandas 读取文件 当使用 Pandas 做数据分析的时,需要读取事先准备好的数据集,这是做数据分析的第一步。Panda 提…...

微服务的异步通信技术RabbitMQ
文章目录前言1.WorkQueue(工作队列)消息预取机制2.Publish&Subscribe(发布-订阅)1.Fanout(广播)2.DirectExchange(路由)3.TopicExchange(话题)MQ的优点前…...

Word处理控件Aspose.Words功能演示:使用 C++ 在 Word (DOC/DOCX) 中添加或删除水印
Aspose.Words 是一种高级Word文档处理API,用于执行各种文档管理和操作任务。API支持生成,修改,转换,呈现和打印文档,而无需在跨平台应用程序中直接使用Microsoft Word。此外, Aspose API支持流行文件格式处…...

chatGPT模型原理
文章目录简介BertGPT 初代GPT-2GPT-3chatGPT开源ChatGPT简介 openai 的 GPT 大模型的发展历程。 Bert 2018年,自然语言处理 NLP 领域也步入了 LLM 时代,谷歌出品的 Bert 模型横空出世,碾压了以往的所有模型,直接在各种NLP的建模…...

四、阻塞队列
文章目录基础概念生产者消费者概念JUC阻塞队列的存取方法ArrayBlockingQueueArrayBlockingQueue的基本使用生产者方法实现原理ArrayBlockingQueue的常见属性add方法实现offer方法实现offer(time,unit)方法put方法消费者方法实现原理remove方法poll方法poll(time,unit)方法take方…...

企业电子招投标采购系统源码之登录页面
信息数智化招采系统 服务框架:Spring Cloud、Spring Boot2、Mybatis、OAuth2、Security 前端架构:VUE、Uniapp、Layui、Bootstrap、H5、CSS3 涉及技术:Eureka、Config、Zuul、OAuth2、Security、OSS、Turbine、Zipkin、Feign、Monitor、…...

SQL零基础入门学习(十三)
上一篇(SQL零基础入门学习(十二)) SQL 视图(Views) 视图是可视化的表。 SQL CREATE VIEW 语句 在 SQL 中,视图是基于 SQL 语句的结果集的可视化的表。 视图包含行和列,就像一个…...

Java实现简单KV数据库
用Java实现一个简单的KV数据库 开发思路: 用map存储数据,再用一个List记录操作日志,开一个新线程将List中的操作写入日志文件中,再开一个线程用于网络IO服务接收客户端的命令,再启动时检查日志,如果有数据就…...

【Spark分布式内存计算框架——Spark Streaming】5. DStream(上)
3. DStream SparkStreaming模块将流式数据封装的数据结构:DStream(Discretized Stream,离散化数据流,连续不断的数据流),代表持续性的数据流和经过各种Spark算子操作后的结果数据流。 3.1 DStream 是什么…...

Spring系列-9 Async注解使用与原理
背景: 本文作为Spring系列的第九篇,介绍Async注解的使用、注意事项和实现原理,原理部分会结合Spring框架代码进行。 本文可以和Spring系列-8 AOP原理进行比较阅读 1.使用方式 Async一般注解在方法上,用于实现方法的异步…...

Python自动化测试实战篇(6)用PO分层模式及思想,优化unittest+ddt+yaml+request登录接口自动化测试
这些是之前的文章,里面有一些基础的知识点在前面由于前面已经有写过,所以这一篇就不再详细对之前的内容进行描述 Python自动化测试实战篇(1)读取xlsx中账户密码,unittest框架实现通过requests接口post登录网站请求&…...

Linux 进程:父子进程
目录一、了解子进程二、创建子进程1.创建子进程2.区分父子进程三、理解子进程四、创建子进程的意义进程就是运行中的应用程序,如果一个程序较为庞大,我们可以给这个程序创建多个进程,每个进程负责一部分代码的运行。 A进程如果创建了B进程&am…...

Unity 之 实现读取代码写进Word文档功能实现 -- 软著脚本生成工具
Unity 之 实现读取代码写进Word文档功能前言一,实现步骤1.1 逻辑梳理1.2 用到工具二,实现读写文件2.1 读取目录相关2.2 读写文件三,编辑器拓展3.1 编辑器拓展介绍3.2 实现界面可视化四,源码分享4.1 工具目录4.2 完整代码前言 之所…...

Typora图床配置:Typora + PicGo + 阿里云OSS
文章目录一、前景提要二、相关链接三、搭建步骤1. 购买阿里云对象存储OSS2. 对象存储OSS:创建Bucket3. 阿里云:添加OSS访问用户及权限4. 安装Typora5. 配置PicGo方法一:使用PicGo-Core (Command line)方法二:使用PicGo(app)6. 最后…...
二进制搭建以太坊2.0节点-2023最新详细版文档
文章目录 一、配置 JWT 认证二、部署执行节点geth2.1 下载geth二进制文件2.2 geth节点启动三、部署共识节点Prysm3.1 下载Prysm脚本3.2 Prysm容器生成四、检查节点是否同步完成4.1 检查geth执行节点4.2 检查prysm共识节点4.3 geth常用命令五、节点同步详细说明5.1 启动时日志5.…...

如何简化跨网络安全域的文件发送流程,大幅降低IT人员工作量?
为什么要做安全域的隔离? 随着企业数字化转型的逐步深入,企业投入了大量资源进行信息系统建设,信息化程度日益提升。在这一过程中,企业也越来越重视核心数据资产的保护,数据资产的安全防护成为企业面临的重大挑战。 …...

带你深入了解c语言指针后续
前言 🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏: 🍔🍟🌯 c语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介:>:介绍c语言中有关指针更深层的知识. 金句分享: ✨在该…...

借助Intune无感知开启Bitlocker
希望使用 Intune 部署 BitLocker,但不知道从哪里开始?这是人们最开始使用 Intune 时最常见的问题之一。在本博客中,你将了解有关使用 Intune 管理 BitLocker 的所有信息,包括建议的设置、BitLocker CSP 在客户端上的工作方式&…...

零基础该如何转行Python工程师?学习路线是什么?
最近1年的主要学习时间,都投资到了 python 数据分析和数据挖掘上面来了,虽然经验并不是十分丰富,但希望也能把自己的经验分享下,最近也好多朋友给我留言,和我聊天,问我python该如何学习,才能少走…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...

全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...