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该如何学习,才能少走…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
