2021牛客OI赛前集训营-提高组(第三场) T1变幻
2021牛客OI赛前集训营-提高组(第三场)
题目大意
对于一个大小为nnn的数组aaa的任意一点iii,若满足ai−1>aia_{i-1}>a_iai−1>ai且ai<ai+1a_i<a_{i+1}ai<ai+1,则称iii为山谷点。111和nnn不可能为山谷点。
你最多可以修改最多kkk次数组,每次可以将一个aia_iai的值变小。
求所有山谷点的aaa值之和的最大值。
题解
设fi,jf_{i,j}fi,j表示最后一次修改在点iii或点iii之前,已经修改了jjj次的前iii个数的最大的山谷点的和,那么
- fi,j=fi−1,jf_{i,j}=f_{i-1,j}fi,j=fi−1,j
- 如果aia_iai本来就是山谷点,则fi,j=max(fi,j,fi−2,j+ai)f_{i,j}=\max(f_{i,j},f_{i-2,j}+a_i)fi,j=max(fi,j,fi−2,j+ai)
- 如果j≥1j\geq 1j≥1,则fi,j=max(fi,j,fi−2,j−1+min(ai−1,ai+1)−1)f_{i,j}=\max(f_{i,j},f_{i-2,j-1}+\min(a_{i-1},a_{i+1})-1)fi,j=max(fi,j,fi−2,j−1+min(ai−1,ai+1)−1)
答案为maxi=0kfn−1,i\max\limits_{i=0}^kf_{n-1,i}i=0maxkfn−1,i。
时间复杂度为O(nk)O(nk)O(nk)。
code
#include<bits/stdc++.h>
using namespace std;
int n,k;
long long ans=0,a[2005],f[2005][2005];
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}for(int i=1;i<=n;i++){for(int j=0;j<=n;j++) f[i][j]=-1e18;}f[1][0]=0;for(int i=2;i<n;i++){for(int j=0;j<=k;j++){f[i][j]=f[i-1][j];if(a[i]<a[i-1]&&a[i]<a[i+1]) f[i][j]=max(f[i][j],f[i-2][j]+a[i]);else if(j>=1) f[i][j]=max(f[i][j],f[i-2][j-1]+min(a[i-1],a[i+1])-1);}}for(int i=0;i<=k;i++) ans=max(ans,f[n-1][i]);printf("%lld",ans);return 0;
}
相关文章:
2021牛客OI赛前集训营-提高组(第三场) T1变幻
2021牛客OI赛前集训营-提高组(第三场) 题目大意 对于一个大小为nnn的数组aaa的任意一点iii,若满足ai−1>aia_{i-1}>a_iai−1>ai且ai<ai1a_i<a_{i1}ai<ai1,则称iii为山谷点。111和nnn不可能为山谷点。…...
你还在使用if-else写代码吗,今天带你领略下策略模式的魅力!
1、什么是策略模式 策略模式其实也是在解耦,把策略的定义、创建、使用这三个部分解耦开来,因为本身策略模式也是基于接口编程,这样其实可以简单的理解客户端调用使用接口进行编程,可以通过工厂方法创建对应的策略模式,…...
Leetcode. 21 合并两个有序列表
尾插 核心思路:依次比较 ,取经过比较后较小值进行尾插 cur1 指向list1 ,cur 2指向list2 ,当cur1走完list1 或者cur2 走完list2 后停止 如果cur1走完list1 ,可以将cur2 整个拿下来尾插 如果cur2走完list2 ,可以将cur1 整个拿下来尾插 特殊情况 ࿱…...
使用 Wall 教你搭建 照片墙 和 视频墙
下载 Github:https://github.com/super-tongyao/wall 国内仓库(不推荐,只做加速访问,无编译包和发行版,以github仓库为准):https://gitee.com/Super_TongYao/wall 推荐github仓库,下载最新版…...
0103 MySQL06
1.事务 1.一个事务其实就是一个完整的业务逻辑 如:转账,从A账户向B账户转账10000,将A账户的钱减去10000(update),将B账户的钱加上10000(update),这就是一个完整的业务逻…...
【UE4 RTS游戏】04-摄像机运动_鼠标移动到视口边缘时移动Pawn
效果可以看到当鼠标移动到视口边缘时,Pawn就会向这个方向移动。步骤打开项目设置,添加两个操作映射打开“CameraPawnController”,在事件图表中添加两个浮点型变量,一个为公有一个为私有。分别命名为“ZoomSensitivity”、“MaxAr…...
147597-66-8,p-SCN-Bn-NOTA,NOTA-P-苯-NCS新型双功能螯合剂
p-SCN-Bn-NOTA | NOTA-P-苯-NCS | CAS:147597-66-8 | 纯度:95%1.p-SCN-Bn-NOTA试剂信息:CAS号:147597-66-8外观:白色固体分子量:C20H26N4O6S分子式:448.4928溶解性:溶于有机溶剂&…...
JDK解压安装及idea开发工具配置
1. 安装JDK 1.1 下载安装包 下载安装包,直接解压,注意,解压的路径不要有中文 1.2 配置环境变量 右键点击我的电脑,选择属性 选择高级系统设置 选择环境变量 选择新建 在变量名中输入JAVA_HOME,变量值就是1.1中压缩包…...
使用Ubuntu中的Docker部署Remix
一、简介1.博主这里使用的是腾讯云的服务,然后使用Docker进行部署Remix。2.踩了几个坑,没有花费过多时间,所以这篇文章会记录踩过的坑。然后避免你们掉进去,然后花费过多时间。3.这里就不写怎么安装Docker了,因为博主上…...
【MySQL】P9 多表查询(3) - 子查询
子查询子查询基本概念(公式)子查询分类按照结果分类标量 子查询列 子查询行 子查询表 子查询子查询 基本概念(公式) SQL查询语句中嵌套Select语句,称为嵌套查询,亦称为子查询; select * from…...
SpringMVC中的拦截器不生效的问题解决以及衍生出的WebMvcConfigurationSupport继承问题思考
文章目录SpringMVC中的拦截器不生效的问题解决WebMvcConfigurationSupport继承问题思考SpringMVC中的拦截器不生效的问题解决 过滤器代码(被Spring扫描并管理): Component public class StuInterceptor implements HandlerInterceptor {Overridepublic boolean pr…...
【量化交易笔记】3.实现数据库保存数据
上一节,我们通过下载相关的 pandas 数据保存为 本地csv文件,这一节将上节的数据以数据库方式保存。 数据库保存 采集数据部分前一节已做说明,这里就直接用采用前面的内容。这里着重说明的事数据库连接。对与 python 相连接的数据库有很多&a…...
[数据结构]:15-堆排序(顺序表指针实现形式)(C语言实现)
目录 前言 已完成内容 堆排序实现 01-开发环境 02-文件布局 03-代码 01-主函数 02-头文件 03-PSeqListFunction.cpp 04-SortCommon.cpp 05-SortFunction.cpp 结语 前言 此专栏包含408考研数据结构全部内容,除其中使用到C引用外,全为C语言代码…...
蓝桥 卷“兔”来袭编程竞赛专场-02破解曾公亮密码 题解
赛题介绍 挑战介绍 曾公亮编撰的《武经总要》中记载了一套严谨的军事通信密码,这也是目前发现我国古代战争中最早使用的军用密码表。将战场上可能常用到的情况,用 40 个短语归纳表示,且每个短语前编有固定的数字代码,这 40 个短…...
CSS定位
🍓个人主页:bit.. 🍒系列专栏:Linux(Ubuntu)入门必看 C语言刷题 数据结构与算法 HTML和CSS3 目录 1.1为什么需要定位? 1.2定位组成 1.3静态定位static(了解) 1.4相对定位 relative …...
python sympy库
sympy库是python的符号运算库,是电脑辅助简单数学函数计算的好工具。本文简单记录了一下有关sympy的方法。建议使用jupyter notebook,这样输出的函数很好看。 文章目录sympy基础安装自变量(Symbols)函数表达式(Expr&am…...
达梦数据库统计信息的导出导入
一、统计信息对象统计信息描述了对象数据的分布特征。统计信息是优化器的代价计算的依据,可以帮助优化器较精确地估算成本,对执行计划的选择起着至关重要的作用。统计信息的收集频率是一把双刃剑,频率太低导致统计信息滞后,频率太…...
信息系统基本知识(六)
大纲 信息系统与信息化信息系统开发方法常规信息系统集成技术软件工程新一代信息技术信息系统安全技术信息化发展与应用信息系统服务管理信息系统服务规划企业首席信息管及其责任 1.7 信息化发展与应用 我国在“十三五”规划纲要中,将培育人工智能、移动智能终端…...
<C++>智能指针
1. 智能指针 #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<memory> using namespace std;int div() {int a, b;cin >> a >> b;if (b 0)throw invalid_argument("除0错误");return a / b; }void func() {int* p1 new in…...
1.分析vmlinux可执行文件是如何生成的? 2.整理内核编译流程:uImage/zImage/Image/vmlinx之间关系
一、分析vmlinux可执行文件是如何生成的? 1、分析内核的底层 makefile 如下: vmlinux: scripts/link-vmlinux.sh vmlinux_prereq $(vmlinux-deps) FORCE$(call if_changed,link-vmlinux)vmlinux_prereq: $(vmlinux-deps) FORCE发现vmlinux的生成主要依…...
Android Studio中文插件:3分钟极速汉化,告别英文开发障碍
Android Studio中文插件:3分钟极速汉化,告别英文开发障碍 【免费下载链接】AndroidStudioChineseLanguagePack AndroidStudio中文插件(官方修改版本) 项目地址: https://gitcode.com/gh_mirrors/an/AndroidStudioChineseLanguagePack …...
AI大模型时代:微店商品数据API如何重构反向海淘决策
在AI大模型时代,微店商品数据API凭借覆盖下沉市场、小众货源、私域供给的独特优势,成为重构反向海淘决策的核心支撑,将传统“人工经验判断”升级为“数据采集→AI分析→自动决策→反馈优化”的全链路数据驱动模式,大幅提升选品精准…...
2026论文写作工具红黑榜:一键生成论文工具怎么选?别再瞎找了!
2026年论文写作工具红黑榜出炉!红榜优先选千笔AI、ThouPen、豆包,适配国内学术规范,内容严谨可靠;黑榜需避开低质免费工具、无真实引用平台、过度依赖全文生成的工具。选择时可参考三维模型:需求匹配度 - 数据可信度 -…...
2025.12晶晨S905L3S-L3SB安卓9通刷实战:当贝桌面加持,解锁多品牌盒子新玩法
1. 晶晨S905L3S-L3SB通刷包的前世今生 第一次听说晶晨S905L3S-L3SB芯片能通刷时,我正对着家里三台不同品牌的电视盒子发愁。这些盒子有的来自运营商赠送,有的是二手市场淘来的,虽然硬件配置相近,但系统体验天差地别。直到发现这个…...
Pixel Couplet Gen 生成效果对比分析:不同参数下的对联质量评估
Pixel Couplet Gen 生成效果对比分析:不同参数下的对联质量评估 1. 引言:当AI遇上传统对联 春节贴对联是中国延续千年的文化传统,但创作一副既工整又有新意的对联并非易事。Pixel Couplet Gen作为一款AI对联生成工具,通过调整Te…...
掌握TegraRcmGUI:从入门到精通的Switch注入实践指南
掌握TegraRcmGUI:从入门到精通的Switch注入实践指南 【免费下载链接】TegraRcmGUI C GUI for TegraRcmSmash (Fuse Gele exploit for Nintendo Switch) 项目地址: https://gitcode.com/gh_mirrors/te/TegraRcmGUI TegraRcmGUI是一款基于C开发的图形化界面工具…...
从云端到指尖:巧用Aspose组件实现Office/PDF文档秒级HTML预览,攻克移动端大文件访问瓶颈
1. 移动端大文件预览的痛点与解决思路 最近接手一个企业级项目时,遇到了一个非常典型的场景:用户通过PC端上传各种办公文档(Word、Excel、PPT、PDF),需要在移动端随时查看。但当文件体积较大时(比如超过50M…...
新手福音:用快马平台将vmware官网概念转化为可交互的虚拟机演示代码
作为一名刚接触虚拟化技术的新手,我最近在VMware官网上看到了关于虚拟机的基础概念介绍。虽然理论知识很全面,但总觉得少了点动手实践的环节。直到发现了InsCode(快马)平台,它让我能够把抽象的概念快速转化为可运行的代码,这种学习…...
YOLOv8预测结果一键导出:自定义路径+日期文件夹,还能合并所有标签到单个TXT文件
YOLOv8预测结果高效管理:自动化归档与标签合并实战指南 当你在使用YOLOv8完成目标检测任务后,是否经常遇到这样的困扰:检测结果散落在不同文件夹中难以追溯,标签文件分散在各个角落不便统计,每次手动整理既耗时又容易出…...
Venera漫画阅读器:跨平台智能阅读的终极指南
Venera漫画阅读器:跨平台智能阅读的终极指南 【免费下载链接】venera A comic app 项目地址: https://gitcode.com/gh_mirrors/ve/venera 想要在Android、iOS、Windows、macOS和Linux上享受无缝的漫画阅读体验吗?Venera漫画阅读器正是您需要的终极…...
