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

动态规划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. 登山 题目描述 五一到了&#xff0c;ACM队组织大家去登山观光&#xff0c;队员们发现山上一共有N个景点&#xff0c;并且决定按照顺序来浏览这些景点&#xff0c;即每次所浏览景点的编号都要大于前一个…...

css-设置元素的溢出行为为可见overflow: visible;

1.前言 overflow 属性用于设置当元素的内容溢出其框时如何处理。 2. overflow overflow 属性的一些常见值&#xff1a; 1 visible&#xff1a;默认值。内容不会被剪裁&#xff0c;会溢出元素的框。 2 hidden&#xff1a;内容会被剪裁&#xff0c;不会显示溢出的部分。 3 sc…...

家居EDI:Hom Furniture EDI需求分析

HOM Furniture 是一家成立于1977年的美国家具零售商&#xff0c;总部位于明尼苏达州。公司致力于提供高品质、时尚的家具和家居用品&#xff0c;满足各种家庭和办公需求。HOM Furniture 以广泛的产品线和优质的客户服务在市场上赢得了良好的口碑。公司经营的产品包括卧室、客厅…...

1、开始简单使用rag

文章目录 前言数据存放申请api开始代码安装依赖从文件夹中读取文档文档切块将分割嵌入并存储在向量库中检索部分代码构造用户接口演示提示 整体代码 前言 本章只是简单使用rag的一个示例&#xff0c;为了引出以后的学习&#xff0c;将整个rag的流程串起来 数据存放 一个示例…...

Linux Samba 低版本漏洞(远程控制)复现与剖析

目录 前言 漏洞介绍 漏洞原理 产生条件 漏洞影响 防御措施 复现过程 结语 前言 在网络安全的复杂生态中&#xff0c;系统漏洞的探索与防范始终是保障数字世界安全稳定运行的关键所在。Linux Samba 作为一款在网络共享服务领域应用极为广泛的软件&#xff0c;其低版本中…...

安卓(android)实现注册界面【Android移动开发基础案例教程(第2版)黑马程序员】

一、实验目的&#xff08;如果代码有错漏&#xff0c;可查看源码&#xff09; 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 处理 错误分析&#xff1a; 5.综合对比示例 最后总结 注意事项 引言 instanceof 概念在多态中引出&#xff0c;因为在多态发生时&…...

联想拯救者R720笔记本外接显示屏方法,显示屏是2K屏27英寸

晚上23点10分前下单&#xff0c;第二天上午显示屏送到&#xff0c;检查外包装没拆封过。这个屏幕左下方有几个按键&#xff0c;按一按就开屏幕、按一按就关闭屏幕&#xff0c;按一按方便节省时间&#xff0c;也支持阅读等模式。 显示屏是 &#xff1a;AOC 27英寸 2K高清 100Hz…...

【RocketMQ 存储】- 一文总结 RocketMQ 的存储结构-基础

文章目录 1. 前言 本文章基于 RocketMQ 4.9.3 1. 前言 RocketMQ 存储部分系列文章&#xff1a; 【RocketMQ 存储】- RocketMQ存储类 MappedFile 【RocketMQ 存储】- 一文总结 RocketMQ 的存储结构-基础 【RocketMQ 存储】- 一文总结 RocketMQ 的存储结构-基础...

S4 HANA明确税金本币和外币之间转换汇率确定(OBC8)

本文主要介绍在S4 HANA OP中明确明确税金本币和外币之间转换汇率确定(OBC8)相关设置。具体请参照如下内容&#xff1a; 明确税金本币和外币之间转换汇率确定(OBC8) 以上配置&#xff0c;我们可以根据不同公司代码所配置的使用不同的汇率来对税金外币和本币之间进行换算。来针对…...

Cocos Creator 3.8 2D 游戏开发知识点整理

目录 Cocos Creator 3.8 2D 游戏开发知识点整理 1. Cocos Creator 3.8 概述 2. 2D 游戏核心组件 (1) 节点&#xff08;Node&#xff09;与组件&#xff08;Component&#xff09; (2) 渲染组件 (3) UI 组件 3. 动画系统 (1) 传统帧动画 (2) 动画编辑器 (3) Spine 和 …...

梯度提升用于高效的分类与回归

使用 决策树&#xff08;Decision Tree&#xff09; 实现 梯度提升&#xff08;Gradient Boosting&#xff09; 主要是模拟 GBDT&#xff08;Gradient Boosting Decision Trees&#xff09; 的原理&#xff0c;即&#xff1a; 第一棵树拟合原始数据计算残差&#xff08;负梯度…...

【单细胞第二节:单细胞示例数据分析-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. 案例&#xff1a;模板方法模式在数据处理中的应用案例背景UML搭建抽象基类 - 数据处理的 “总指挥”子类定制 - 适配不同供应商供应商 A 的数据处理器供应商 B 的数据处理器 在业务代码中整合运用 8. 总…...

新春登蛇山:告别岁月,启航未来

大年初一&#xff0c;晨曦透过薄雾&#xff0c;温柔地洒在武汉的大街小巷。2025 年的蛇年春节&#xff0c;带着新春的喜气与希望悄然而至。我站在蛇山脚下&#xff0c;心中涌动着复杂的情感&#xff0c;因为今天&#xff0c;我不仅将与家人一起登山揽胜&#xff0c;更将在这一天…...

hive:基本数据类型,关于表和列语法

基本数据类型 Hive 的数据类型分为基本数据类型和复杂数据类型 加粗的是常用数据类型 BOOLEAN出现ture和false外的其他值会变成NULL值 没有number,decimal类似number 如果输入的数据不符合数据类型, 映射时会变成NULL, 但是数据本身并没有被修改 创建表 创建表的本质其实就是在…...

安装最小化的CentOS7后,执行yum命令报错Could not resolve host mirrorlist.centos.org; 未知的错误

文章目录 安装最小化的CentOS7后&#xff0c;执行yum命令报错"Could not resolve host: mirrorlist.centos.org; 未知的错误"错误解决方案&#xff1a; 安装最小化的CentOS7后&#xff0c;执行yum命令报错"Could not resolve host: mirrorlist.centos.org; 未知…...

图论——spfa判负环

负环 图 G G G中存在一个回路&#xff0c;该回路边权之和为负数&#xff0c;称之为负环。 spfa求负环 方法1:统计每个点入队次数, 如果某个点入队n次, 说明存在负环。 证明&#xff1a;一个点入队n次&#xff0c;即被更新了n次。一个点每次被更新时所对应最短路的边数一定是…...

软件工程概论试题三

一、单选 1.需求确认主要检査五个方面的内容&#xff0c;其中那一项是为了保证文档中的需求不互相冲突(即不应该有相互矛盾的约束或者对同一个系统功能有不同的描述)。 A.现实性 B. 可验证性 C.一致性 D.正确性 E.完整性 正答&#xff1a;C 2.下列开发方法中&#xff0c;( )不…...

AI驱动的科研绘图革命:DeTikZify如何终结图表代码的手动时代

AI驱动的科研绘图革命&#xff1a;DeTikZify如何终结图表代码的手动时代 【免费下载链接】DeTikZify Synthesizing Graphics Programs for Scientific Figures and Sketches with TikZ 项目地址: https://gitcode.com/gh_mirrors/de/DeTikZify 当deadline遇上绘图难题&a…...

告别C盘爆满!手把手教你配置Miniforge,让所有虚拟环境乖乖待在D盘

彻底解放C盘空间&#xff1a;Miniforge虚拟环境全迁移至D盘实战指南 每次打开资源管理器看到C盘飘红的存储条&#xff0c;心跳都会漏半拍——这大概是Windows开发者最熟悉的焦虑场景。特别是当你发现conda创建的虚拟环境正悄无声息吞噬着宝贵的系统盘空间时&#xff0c;那种无…...

3个核心技巧:Element Plus效率提升与性能优化指南

3个核心技巧&#xff1a;Element Plus效率提升与性能优化指南 【免费下载链接】element-plus &#x1f389; A Vue.js 3 UI Library made by Element team 项目地址: https://gitcode.com/GitHub_Trending/el/element-plus 副标题&#xff1a;面向初中级开发者的Element…...

别只盯着协议!用TC8测试案例深度解读车载网络中的ARP与ICMP:安全与稳定的隐藏关卡

车载以太网底层协议实战&#xff1a;从TC8测试案例看ARP与ICMP的安全设计 当一辆现代汽车以100km/h行驶时&#xff0c;其车载网络每秒需要处理超过5000条网络报文。这些报文中的绝大多数&#xff0c;都由ARP和ICMP这样的基础协议承载。在传统IT领域被视为"简单"的协议…...

2026年实测10款降AI工具:毕业论文降AIGC哪款最靠谱?

2026年毕业季临近&#xff0c;降低论文AI生成痕迹、通过学校AIGC检测已经成为所有毕业生的必过关卡。但当前降AI工具市场鱼龙混杂&#xff1a;不少用户花了高价处理&#xff0c;AI率却纹丝不动&#xff1b;还有的工具改完的论文语句生硬、逻辑混乱&#xff0c;反而过不了答辩。…...

Zabbix 6.0部署避坑指南:为什么你的Ubuntu安装总卡在数据库初始化这一步?

Zabbix 6.0部署避坑指南&#xff1a;为什么你的Ubuntu安装总卡在数据库初始化这一步&#xff1f; 如果你正在Ubuntu上部署Zabbix 6.0&#xff0c;却反复在数据库初始化这一步失败&#xff0c;这篇文章就是为你准备的。不同于常规的安装教程&#xff0c;我们将聚焦于那些看似简…...

避坑指南:通达信DLL加密常见的5大误区与替代方案

通达信指标加密实战&#xff1a;5种DLL开发陷阱与零代码解决方案 在量化交易领域&#xff0c;指标公式的保护一直是开发者面临的棘手问题。最近三个月内&#xff0c;某金融开发者社区关于"通达信DLL加密失败"的求助帖增长了47%&#xff0c;暴露出传统加密方案存在显…...

Python: 多优化算法TSP求解方案,物流路径规划代码实践 - 附详尽注释及标准数据集

Python&#xff1a;模拟退火算法、蚁群算法、遗传算法、粒子群算法求解旅行商问题(TSP)的Python代码程序。 物流路径规划问题。 -- 数据集采用的tsplib标准数据集&#xff0c;可以根据自己需求修改城市坐标。 代码完整&#xff0c;注释详细&#xff0c;打印每次迭代结果&#x…...

Godot-MCP:如何通过双向语义桥梁解决游戏开发中的创意断层问题

Godot-MCP&#xff1a;如何通过双向语义桥梁解决游戏开发中的创意断层问题 【免费下载链接】Godot-MCP An MCP for Godot that lets you create and edit games in the Godot game engine with tools like Claude 项目地址: https://gitcode.com/gh_mirrors/god/Godot-MCP …...

Mac用户的移动Win10工坊:从WTG配置到驱动、激活、文件共享的完整避坑指南

Mac用户的移动Win10工坊&#xff1a;从WTG配置到驱动、激活、文件共享的完整避坑指南 当Mac用户需要运行Windows应用时&#xff0c;双系统方案往往是最佳选择。而通过Windows To Go&#xff08;WTG&#xff09;技术将Win10安装在移动硬盘上&#xff0c;不仅保留了Mac原生系统的…...