洛谷 P1725 琪露诺 单调队列优化的线性dp

ops/2025/3/16 15:20:44/

==========以上是题目====

考虑到2e5的数据范围,暴力的先枚举i,在枚举走的步数区间j,是过不了的,

我们可以看出对于每一个i,只需要找出能走的i的区间的dp最大值即可,求区间最大值可以使用单调队列,时间复杂度就是O(n)的
 

注意:a[]有负数,所以要把dp[]和ans都初始化为负数

const int N = 2e5 + 10;LL n,L,R;
LL dp[N],a[N],dq[N];
int hh = 1,tt = 0;void solve()
{cin >> n >> L >> R;for (int i = 0;i <= n;i ++) cin >> a[i];LL ans = -inf;memset(dp,-0x3f,sizeof dp);dp[0] = 0;for (int i = L;i <= n;i ++){while(hh <= tt && dq[hh] < i - R) hh ++;//队头合法性while(hh <= tt && dp[dq[tt]] < dp[i - L]) tt --;//队尾dp值<距离i最近的dp值dq[++tt] = i - L;dp[i] = dp[dq[hh]] + a[i];//队头最优if (i + R > n) //如果能过桥就更新ansans = max(ans,dp[i]);}cout << ans << endl;}

 


http://www.ppmy.cn/ops/166231.html

相关文章

江科大51单片机笔记【12】AT24C02(I2C总线)

写在前言 此为博主自学江科大51单片机&#xff08;B站&#xff09;的笔记&#xff0c;方便后续重温知识 在后面的章节中&#xff0c;为了防止篇幅过长和易于查找&#xff0c;我把一个小节分成两部分来发&#xff0c;上章节主要是关于本节课的硬件介绍、电路图、原理图等理论知识…

【Linux】UDP协议与TCP协议

目录 一、端口号 &#xff08;一&#xff09;端口号划分 &#xff08;二&#xff09;端口号相关概念 二、相关指令 &#xff08;一&#xff09;pidof &#xff08;二&#xff09;netstat 三、UDP协议 &#xff08;一&#xff09;UDP协议格式 &#xff08;二&#xff09…

vue 仿deepseek前端开发一个对话界面

后端&#xff1a;调用deepseek的api&#xff0c;所以返回数据格式和deepseek相同 {"model": "DeepSeek-R1-Distill-Qwen-1.5B", "choices": [{"index": 0, "delta": {"role": "assistant", "cont…

便捷搞定计算机名、IP 与 Mac 地址修改及网卡问题的软件

今天要给大家推荐一款超实用的小软件——“IPtool”。别看它体积小巧&#xff0c;还不到 1M&#xff0c;而且是绿色单文件版&#xff0c;无需复杂安装&#xff0c;使用起来却相当给力&#xff0c;能帮我们轻松搞定一些日常网络设置中的小麻烦。 在修改 IP 地址这件事上&#xf…

JVM 2015/3/15

定义&#xff1a;Java Virtual Machine -java程序的运行环境&#xff08;java二进制字节码的运行环境&#xff09; 好处&#xff1a; 一次编写&#xff0c;到处运行 自动内存管理&#xff0c;垃圾回收 数组下标越界检测 多态 比较&#xff1a;jvm/jre/jdk 常见的JVM&…

Qt QML实现弹球消砖块小游戏

前言 弹球消砖块游戏想必大家都玩过&#xff0c;很简单的小游戏&#xff0c;通过移动挡板反弹下落的小球&#xff0c;然后撞击砖块将其消除。本文使用QML来简单实现这个小游戏。 效果图&#xff1a; 正文 代码目录结构如下&#xff1a; 首先是小球部分&#xff0c;逻辑比较麻…

现代密码学 | 具有数字签名功能的安全方案

1.案例背景 1.1冒用签名触发信任危机&#xff0c;360安全大脑率先截杀解除警报 2020年8月&#xff0c;360安全大脑独家发现冒用数字签名的网络攻击再度活跃&#xff0c;且继此前360安全大脑披露过的Go Daddy、Starfield Secure、赛门铁克、Verisign和DigiCert等国际知名CA证书…

C++初阶——类和对象(二)

C初阶——类和对象&#xff08;二&#xff09; 本期内容书接上回&#xff0c;继续讨论类和对象相关内容。类和对象属于C初阶部分&#xff0c;主要反映了面向对象编程的三大基本特点之一——封装&#xff0c;在C的学习中占有举足轻重的地位&#xff01; 一、类对象模型 1.如何…