[題解](單調隊列dp)luogu_P1725琪露諾
2024-10-21 09:34:22
比較簡單的單調隊列,但是有一些要注意的
維護單調隊列的時候裡面存的是入隊時間,而不是i,因為前面有l個沒有入隊(不可能走進),所以把i减一个l以达到延迟入队的效果
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int n,l,r,a[maxn];
int q[maxn],head=,tail=;
int f[maxn];
int main()
{
scanf("%d%d%d",&n,&l,&r);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=l;i<=n;i++){
while(head<=tail && q[head]+r<i)head++;
while(head<=tail && f[q[tail]]<f[i-l])tail--;
q[++tail]=i-l;//不能直接用i,不然記個p當做時間也行(一樣效果
f[i]=f[q[head]]+a[i];
}
int ans=;
for(int i=n+-r;i<=n;i++)ans=max(ans,f[i]);
printf("%d",ans);
}
最新文章
- laravel中如何防止直接访问.env文件
- 优先队列 :Priority Queue
- MyBatis学习(四)、MyBatis配置文件
- Apple移动设备处理器指令集 armv6、armv7、armv7s及arm64
- jquery中的prop和attr比较区别
- $_ 与 $PSItem
- 【恒天云技术分享系列11】Sheepdog简介
- Codeforces Round #331 (Div. 2) D. Wilbur and Trees 记忆化搜索
- Android之手机屏幕的获取
- 201521123052《Java程序设计》第10周学习总结
- Oracle Global Finanicals Technical Reference(二)
- .net js有数据 但是跳转不到操作页
- jsp页面<;%@ page报错问题
- html5 知识点简单总结02
- Zabbix4.2.0使用Python连接企业微信报警
- 更换Grade源为阿里云解决下载慢问题
- git server 搭建指南
- nodejs调用脚本(python/shell)和系统命令
- win7(64)使用vim碰到的奇怪问题
- 关于vue路由嵌套遇到的坑~