动态规划DP 最长上升子序列模型 登山(题目分析+C++完整代码)
概览检索
动态规划DP 最长上升子序列模型
登山
原题链接
AcWing 1014. 登山
题目描述
五一到了,ACM队组织大家去登山观光,队员们发现山上一共有N个景点,并且决定按照顺序来浏览这些景点,即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯,就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了。
队员们希望在满足上面条件的同时,尽可能多的浏览景点,你能帮他们找出最多可能浏览的景点数么?
输入格式
第一行包含整数N,表示景点数量。
第二行包含N个整数,表示每个景点的海拔。
输出格式
输出一个整数,表示最多能浏览的景点数。
数据范围
2≤N≤1000
输入样例:
8
186 186 150 200 160 130 197 220
输出样例:
4
题目分析
题目要求:
1. 编号递增
2. 海拔不连续相同
3. 海拔一旦开始下降,就不再上升
由1可知该序列为子序列,由2,3可知,路径路线一定是严格的先上升后下降,画出示意图如下:

看到这个示意图是否有些熟悉?由此,我们联想到 怪盗基德的滑翔伞 (点击链接跳转题目)。

区别在于,
怪盗基德的滑翔伞 是求出左半部分和右半部分的最大值后,二者再取最大值。
登山 是求出左半部分和右半部分的所有值后二者相加取和的最大值。
完整代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n;
int a[N],f[N],g[N];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);//左半部分的递增子序列for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<i;j++)if(a[j]<a[i])f[i]=max(f[i],f[j]+1);}//右半部分的递减子序列for(int i=n;i>=1;i--){g[i]=1;for(int j=n;j>i;j--)if(a[j]<a[i])g[i]=max(g[i],g[j]+1);}int res=0;//最终结果为二者相加取最大值for(int i=1;i<=n;i++) res=max(res,f[i]+g[i]-1); //-1为高峰重复计算printf("%d",res);return 0;
}
相关文章:
动态规划DP 最长上升子序列模型 登山(题目分析+C++完整代码)
概览检索 动态规划DP 最长上升子序列模型 登山 原题链接 AcWing 1014. 登山 题目描述 五一到了,ACM队组织大家去登山观光,队员们发现山上一共有N个景点,并且决定按照顺序来浏览这些景点,即每次所浏览景点的编号都要大于前一个…...
css-设置元素的溢出行为为可见overflow: visible;
1.前言 overflow 属性用于设置当元素的内容溢出其框时如何处理。 2. overflow overflow 属性的一些常见值: 1 visible:默认值。内容不会被剪裁,会溢出元素的框。 2 hidden:内容会被剪裁,不会显示溢出的部分。 3 sc…...
家居EDI:Hom Furniture EDI需求分析
HOM Furniture 是一家成立于1977年的美国家具零售商,总部位于明尼苏达州。公司致力于提供高品质、时尚的家具和家居用品,满足各种家庭和办公需求。HOM Furniture 以广泛的产品线和优质的客户服务在市场上赢得了良好的口碑。公司经营的产品包括卧室、客厅…...
1、开始简单使用rag
文章目录 前言数据存放申请api开始代码安装依赖从文件夹中读取文档文档切块将分割嵌入并存储在向量库中检索部分代码构造用户接口演示提示 整体代码 前言 本章只是简单使用rag的一个示例,为了引出以后的学习,将整个rag的流程串起来 数据存放 一个示例…...
Linux Samba 低版本漏洞(远程控制)复现与剖析
目录 前言 漏洞介绍 漏洞原理 产生条件 漏洞影响 防御措施 复现过程 结语 前言 在网络安全的复杂生态中,系统漏洞的探索与防范始终是保障数字世界安全稳定运行的关键所在。Linux Samba 作为一款在网络共享服务领域应用极为广泛的软件,其低版本中…...
安卓(android)实现注册界面【Android移动开发基础案例教程(第2版)黑马程序员】
一、实验目的(如果代码有错漏,可查看源码) 1.掌握LinearLayout、RelativeLayout、FrameLayout等布局的综合使用。 2.掌握ImageView、TextView、EditText、CheckBox、Button、RadioGroup、RadioButton、ListView、RecyclerView等控件在项目中的…...
【 AI agents】letta:2024年代理堆栈演进(中英文翻译)
The AI agents stack AI 代理堆栈 November 14, 2024 11月 14, 2024原文: The AI agents stack官方教程教程学习笔记: 【memgpt】letta 课程1/2:从头实现一个自我编辑、记忆和多步骤推理的代理Understanding the AI agents landscape 了解 AI 代理环境 Although we see a …...
Java中 instanceof 的用法(详解)
目录 引言 基本语法 基本作用 1. 检查对象是否是指定类的实例 2. 检查对象是否是子类的实例 3. 检查对象是否实现某个接口 4.null 处理 错误分析: 5.综合对比示例 最后总结 注意事项 引言 instanceof 概念在多态中引出,因为在多态发生时&…...
联想拯救者R720笔记本外接显示屏方法,显示屏是2K屏27英寸
晚上23点10分前下单,第二天上午显示屏送到,检查外包装没拆封过。这个屏幕左下方有几个按键,按一按就开屏幕、按一按就关闭屏幕,按一按方便节省时间,也支持阅读等模式。 显示屏是 :AOC 27英寸 2K高清 100Hz…...
【RocketMQ 存储】- 一文总结 RocketMQ 的存储结构-基础
文章目录 1. 前言 本文章基于 RocketMQ 4.9.3 1. 前言 RocketMQ 存储部分系列文章: 【RocketMQ 存储】- RocketMQ存储类 MappedFile 【RocketMQ 存储】- 一文总结 RocketMQ 的存储结构-基础 【RocketMQ 存储】- 一文总结 RocketMQ 的存储结构-基础...
S4 HANA明确税金本币和外币之间转换汇率确定(OBC8)
本文主要介绍在S4 HANA OP中明确明确税金本币和外币之间转换汇率确定(OBC8)相关设置。具体请参照如下内容: 明确税金本币和外币之间转换汇率确定(OBC8) 以上配置,我们可以根据不同公司代码所配置的使用不同的汇率来对税金外币和本币之间进行换算。来针对…...
Cocos Creator 3.8 2D 游戏开发知识点整理
目录 Cocos Creator 3.8 2D 游戏开发知识点整理 1. Cocos Creator 3.8 概述 2. 2D 游戏核心组件 (1) 节点(Node)与组件(Component) (2) 渲染组件 (3) UI 组件 3. 动画系统 (1) 传统帧动画 (2) 动画编辑器 (3) Spine 和 …...
梯度提升用于高效的分类与回归
使用 决策树(Decision Tree) 实现 梯度提升(Gradient Boosting) 主要是模拟 GBDT(Gradient Boosting Decision Trees) 的原理,即: 第一棵树拟合原始数据计算残差(负梯度…...
【单细胞第二节:单细胞示例数据分析-GSE218208】
GSE218208 1.创建Seurat对象 #untar(“GSE218208_RAW.tar”) rm(list ls()) a data.table::fread("GSM6736629_10x-PBMC-1_ds0.1974_CountMatrix.tsv.gz",data.table F) a[1:4,1:4] library(tidyverse) a$alias:gene str_split(a$alias:gene,":",si…...
设计模式 - 行为模式_Template Method Pattern模板方法模式在数据处理中的应用
文章目录 概述1. 核心思想2. 结构3. 示例代码4. 优点5. 缺点6. 适用场景7. 案例:模板方法模式在数据处理中的应用案例背景UML搭建抽象基类 - 数据处理的 “总指挥”子类定制 - 适配不同供应商供应商 A 的数据处理器供应商 B 的数据处理器 在业务代码中整合运用 8. 总…...
新春登蛇山:告别岁月,启航未来
大年初一,晨曦透过薄雾,温柔地洒在武汉的大街小巷。2025 年的蛇年春节,带着新春的喜气与希望悄然而至。我站在蛇山脚下,心中涌动着复杂的情感,因为今天,我不仅将与家人一起登山揽胜,更将在这一天…...
hive:基本数据类型,关于表和列语法
基本数据类型 Hive 的数据类型分为基本数据类型和复杂数据类型 加粗的是常用数据类型 BOOLEAN出现ture和false外的其他值会变成NULL值 没有number,decimal类似number 如果输入的数据不符合数据类型, 映射时会变成NULL, 但是数据本身并没有被修改 创建表 创建表的本质其实就是在…...
安装最小化的CentOS7后,执行yum命令报错Could not resolve host mirrorlist.centos.org; 未知的错误
文章目录 安装最小化的CentOS7后,执行yum命令报错"Could not resolve host: mirrorlist.centos.org; 未知的错误"错误解决方案: 安装最小化的CentOS7后,执行yum命令报错"Could not resolve host: mirrorlist.centos.org; 未知…...
图论——spfa判负环
负环 图 G G G中存在一个回路,该回路边权之和为负数,称之为负环。 spfa求负环 方法1:统计每个点入队次数, 如果某个点入队n次, 说明存在负环。 证明:一个点入队n次,即被更新了n次。一个点每次被更新时所对应最短路的边数一定是…...
软件工程概论试题三
一、单选 1.需求确认主要检査五个方面的内容,其中那一项是为了保证文档中的需求不互相冲突(即不应该有相互矛盾的约束或者对同一个系统功能有不同的描述)。 A.现实性 B. 可验证性 C.一致性 D.正确性 E.完整性 正答:C 2.下列开发方法中,( )不…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
