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

2021牛客OI赛前集训营-提高组(第三场) T1变幻

2021牛客OI赛前集训营-提高组(第三场)

题目大意

对于一个大小为nnn的数组aaa的任意一点iii,若满足ai−1>aia_{i-1}>a_iai1>aiai<ai+1a_i<a_{i+1}ai<ai+1,则称iii为山谷点。111nnn不可能为山谷点。

你最多可以修改最多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=fi1,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,fi2,j+ai)
  • 如果j≥1j\geq 1j1,则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,fi2,j1+min(ai1,ai+1)1)

答案为max⁡i=0kfn−1,i\max\limits_{i=0}^kf_{n-1,i}i=0maxkfn1,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赛前集训营-提高组&#xff08;第三场&#xff09; 题目大意 对于一个大小为nnn的数组aaa的任意一点iii&#xff0c;若满足ai−1>aia_{i-1}>a_iai−1​>ai​且ai<ai1a_i<a_{i1}ai​<ai1​&#xff0c;则称iii为山谷点。111和nnn不可能为山谷点。…...

你还在使用if-else写代码吗,今天带你领略下策略模式的魅力!

1、什么是策略模式 策略模式其实也是在解耦&#xff0c;把策略的定义、创建、使用这三个部分解耦开来&#xff0c;因为本身策略模式也是基于接口编程&#xff0c;这样其实可以简单的理解客户端调用使用接口进行编程&#xff0c;可以通过工厂方法创建对应的策略模式&#xff0c…...

Leetcode. 21 合并两个有序列表

尾插 核心思路&#xff1a;依次比较 &#xff0c;取经过比较后较小值进行尾插 cur1 指向list1 ,cur 2指向list2 ,当cur1走完list1 或者cur2 走完list2 后停止 如果cur1走完list1 ,可以将cur2 整个拿下来尾插 如果cur2走完list2 ,可以将cur1 整个拿下来尾插 特殊情况 &#xff1…...

使用 Wall 教你搭建 照片墙 和 视频墙

下载 Github:https://github.com/super-tongyao/wall 国内仓库&#xff08;不推荐&#xff0c;只做加速访问&#xff0c;无编译包和发行版&#xff0c;以github仓库为准&#xff09;&#xff1a;https://gitee.com/Super_TongYao/wall 推荐github仓库&#xff0c;下载最新版…...

0103 MySQL06

1.事务 1.一个事务其实就是一个完整的业务逻辑 如&#xff1a;转账&#xff0c;从A账户向B账户转账10000&#xff0c;将A账户的钱减去10000&#xff08;update&#xff09;&#xff0c;将B账户的钱加上10000&#xff08;update&#xff09;&#xff0c;这就是一个完整的业务逻…...

【UE4 RTS游戏】04-摄像机运动_鼠标移动到视口边缘时移动Pawn

效果可以看到当鼠标移动到视口边缘时&#xff0c;Pawn就会向这个方向移动。步骤打开项目设置&#xff0c;添加两个操作映射打开“CameraPawnController”&#xff0c;在事件图表中添加两个浮点型变量&#xff0c;一个为公有一个为私有。分别命名为“ZoomSensitivity”、“MaxAr…...

147597-66-8,p-SCN-Bn-NOTA,NOTA-P-苯-NCS新型双功能螯合剂

p-SCN-Bn-NOTA | NOTA-P-苯-NCS | CAS&#xff1a;147597-66-8 | 纯度&#xff1a;95%1.p-SCN-Bn-NOTA试剂信息&#xff1a;CAS号&#xff1a;147597-66-8外观&#xff1a;白色固体分子量&#xff1a;C20H26N4O6S分子式&#xff1a;448.4928溶解性&#xff1a;溶于有机溶剂&…...

JDK解压安装及idea开发工具配置

1. 安装JDK 1.1 下载安装包 下载安装包&#xff0c;直接解压&#xff0c;注意&#xff0c;解压的路径不要有中文 1.2 配置环境变量 右键点击我的电脑&#xff0c;选择属性 选择高级系统设置 选择环境变量 选择新建 在变量名中输入JAVA_HOME&#xff0c;变量值就是1.1中压缩包…...

使用Ubuntu中的Docker部署Remix

一、简介1.博主这里使用的是腾讯云的服务&#xff0c;然后使用Docker进行部署Remix。2.踩了几个坑&#xff0c;没有花费过多时间&#xff0c;所以这篇文章会记录踩过的坑。然后避免你们掉进去&#xff0c;然后花费过多时间。3.这里就不写怎么安装Docker了&#xff0c;因为博主上…...

【MySQL】P9 多表查询(3) - 子查询

子查询子查询基本概念&#xff08;公式&#xff09;子查询分类按照结果分类标量 子查询列 子查询行 子查询表 子查询子查询 基本概念&#xff08;公式&#xff09; SQL查询语句中嵌套Select语句&#xff0c;称为嵌套查询&#xff0c;亦称为子查询&#xff1b; select * from…...

SpringMVC中的拦截器不生效的问题解决以及衍生出的WebMvcConfigurationSupport继承问题思考

文章目录SpringMVC中的拦截器不生效的问题解决WebMvcConfigurationSupport继承问题思考SpringMVC中的拦截器不生效的问题解决 过滤器代码(被Spring扫描并管理)&#xff1a; Component public class StuInterceptor implements HandlerInterceptor {Overridepublic boolean pr…...

【量化交易笔记】3.实现数据库保存数据

上一节&#xff0c;我们通过下载相关的 pandas 数据保存为 本地csv文件&#xff0c;这一节将上节的数据以数据库方式保存。 数据库保存 采集数据部分前一节已做说明&#xff0c;这里就直接用采用前面的内容。这里着重说明的事数据库连接。对与 python 相连接的数据库有很多&a…...

[数据结构]:15-堆排序(顺序表指针实现形式)(C语言实现)

目录 前言 已完成内容 堆排序实现 01-开发环境 02-文件布局 03-代码 01-主函数 02-头文件 03-PSeqListFunction.cpp 04-SortCommon.cpp 05-SortFunction.cpp 结语 前言 此专栏包含408考研数据结构全部内容&#xff0c;除其中使用到C引用外&#xff0c;全为C语言代码…...

蓝桥 卷“兔”来袭编程竞赛专场-02破解曾公亮密码 题解

赛题介绍 挑战介绍 曾公亮编撰的《武经总要》中记载了一套严谨的军事通信密码&#xff0c;这也是目前发现我国古代战争中最早使用的军用密码表。将战场上可能常用到的情况&#xff0c;用 40 个短语归纳表示&#xff0c;且每个短语前编有固定的数字代码&#xff0c;这 40 个短…...

CSS定位

&#x1f353;个人主页&#xff1a;bit.. &#x1f352;系列专栏&#xff1a;Linux(Ubuntu)入门必看 C语言刷题 数据结构与算法 HTML和CSS3 目录 1.1为什么需要定位&#xff1f; 1.2定位组成 1.3静态定位static&#xff08;了解&#xff09; 1.4相对定位 relative …...

python sympy库

sympy库是python的符号运算库&#xff0c;是电脑辅助简单数学函数计算的好工具。本文简单记录了一下有关sympy的方法。建议使用jupyter notebook&#xff0c;这样输出的函数很好看。 文章目录sympy基础安装自变量&#xff08;Symbols&#xff09;函数表达式&#xff08;Expr&am…...

达梦数据库统计信息的导出导入

一、统计信息对象统计信息描述了对象数据的分布特征。统计信息是优化器的代价计算的依据&#xff0c;可以帮助优化器较精确地估算成本&#xff0c;对执行计划的选择起着至关重要的作用。统计信息的收集频率是一把双刃剑&#xff0c;频率太低导致统计信息滞后&#xff0c;频率太…...

信息系统基本知识(六)

大纲 信息系统与信息化信息系统开发方法常规信息系统集成技术软件工程新一代信息技术信息系统安全技术信息化发展与应用信息系统服务管理信息系统服务规划企业首席信息管及其责任 1.7 信息化发展与应用 我国在“十三五”规划纲要中&#xff0c;将培育人工智能、移动智能终端…...

<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可执行文件是如何生成的&#xff1f; 1、分析内核的底层 makefile 如下&#xff1a; vmlinux: scripts/link-vmlinux.sh vmlinux_prereq $(vmlinux-deps) FORCE$(call if_changed,link-vmlinux)vmlinux_prereq: $(vmlinux-deps) FORCE发现vmlinux的生成主要依…...

FreeRTOS数据通信避坑指南:为什么我的MessageBuffer总是接收失败?

FreeRTOS消息缓冲区实战&#xff1a;从接收失败到高效通信的深度解析 第一次在FreeRTOS项目中使用MessageBuffer时&#xff0c;我遇到了一个令人抓狂的问题——明明发送端显示消息已成功写入&#xff0c;接收端却总是返回0字节。调试器显示缓冲区非空&#xff0c;但xMessageBuf…...

CLIP-GmP-ViT-L-14工具实测:如何用图文匹配优化电商搜索与内容审核

CLIP-GmP-ViT-L-14工具实测&#xff1a;如何用图文匹配优化电商搜索与内容审核 1. 图文匹配技术的商业价值 在数字化商业环境中&#xff0c;图片和文字是两种最核心的内容载体。但长期以来&#xff0c;计算机系统很难真正理解两者之间的语义关联。CLIP-GmP-ViT-L-14模型的出现…...

炉石传说自动化脚本终极指南:从3小时到3分钟的游戏体验革命

炉石传说自动化脚本终极指南&#xff1a;从3小时到3分钟的游戏体验革命 【免费下载链接】Hearthstone-Script Hearthstone script&#xff08;炉石传说脚本&#xff09;&#xff08;2024.01.25停更至国服回归&#xff09; 项目地址: https://gitcode.com/gh_mirrors/he/Heart…...

InternLM2-Chat-1.8B助力在线教育:个性化作业批改与学习反馈生成

InternLM2-Chat-1.8B助力在线教育&#xff1a;个性化作业批改与学习反馈生成 1. 引言&#xff1a;当作业批改遇上AI 想象一下&#xff0c;一位老师深夜还在批改几十份、甚至上百份学生作业。面对相似的错误&#xff0c;需要一遍遍写下相同的评语&#xff1b;面对有潜力的答案…...

JMeter vs Claude Code:从“约束系统“到“解放系统“的工程设计范式跃迁

当你还在用 JMeter 写线程组的时候&#xff0c;Claude Code 已经在用自然语言编排测试工作流了。这不是工具的迭代&#xff0c;是工程设计范式的代际更替。前言&#xff1a;两代工程设计哲学的碰撞 2026 年&#xff0c;AI 编程工具已经从"代码生成器"进化为"自主…...

G-Helper完全手册:华硕笔记本终极性能调优指南

G-Helper完全手册&#xff1a;华硕笔记本终极性能调优指南 【免费下载链接】g-helper Lightweight Armoury Crate alternative for Asus laptops. Control tool for ROG Zephyrus G14, G15, G16, M16, Flow X13, Flow X16, TUF, Strix, Scar and other models 项目地址: http…...

AirNgin ESP32 MQTT客户端:面向工业IoT的平台化固件库

1. 项目概述AirNgin ESP32 MQTT Client 是一款专为 ESP32 平台设计的 Arduino 兼容库&#xff0c;面向伊朗本土 IoT 平台 AirNgin 构建。该库并非通用 MQTT 封装&#xff0c;而是深度集成 AirNgin 云平台特有协议栈与管理逻辑的生产级固件组件。其核心价值在于将设备接入、状态…...

从零打造你的CAD开发环境:用OpenCASCADE 7.7.0 + VS2022画个3D盒子(完整Debug/Release配置)

从零打造你的CAD开发环境&#xff1a;用OpenCASCADE 7.7.0 VS2022画个3D盒子&#xff08;完整Debug/Release配置&#xff09; 当你第一次尝试在Visual Studio中配置OpenCASCADE&#xff08;OCCT&#xff09;时&#xff0c;可能会被那些复杂的路径设置、库文件链接和环境变量搞…...

AD5246数字电位器驱动库详解与I²C工程实践

1. AD5246 数字电位器库深度技术解析1.1 器件本质与工程定位AD5246 并非传统意义上的“可编程电阻”&#xff0c;而是一款单通道、IC 接口、128 抽头数字可变电阻器&#xff08;Digital Rheostat&#xff09;。其核心价值在于以数字方式精确控制模拟电路中的阻值&#xff0c;替…...

Sambert多情感语音合成镜像:在虚拟主播场景下的应用实践

Sambert多情感语音合成镜像&#xff1a;在虚拟主播场景下的应用实践 1. 引言&#xff1a;虚拟主播的“声音”难题 你有没有想过&#xff0c;那些在直播间里和你互动、讲段子、带货的虚拟主播&#xff0c;为什么有的声音听起来特别“假”&#xff0c;而有的却能让你感觉像在和…...