2018.10.14 bzoj1915: 奶牛的跳格子游戏(单调队列优化dp)
2024-10-07 00:13:25
传送门
NOIP练习题。
f[i]f[i]f[i]表示去的时候选了iii且回来的时候第一步走的是i−1i-1i−1的最优值。
显然f[i]=maxf[i]=maxf[i]=max{f[j]−sum[j]f[j]-sum[j]f[j]−sum[j]}+sum[i−2]+a[i]+a[i−1]+sum[i-2]+a[i]+a[i-1]+sum[i−2]+a[i]+a[i−1]
直接上单调队列优化就行了。
注意有可能只跳前kkk个直接回到原点的情况。
代码:
#include<bits/stdc++.h>
#define N 250005
#define ll long long
using namespace std;
inline ll read(){
ll ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
int n,k,q[N],hd,tl;
ll ans=0,f[N],a[N],sum[N];
int main(){
n=read(),k=read(),hd=1,tl=0;
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+max((a[i]=read()),0ll);
for(int i=1;i<=n;++i){
while(hd<=tl&&i-q[hd]>k)++hd;
f[i]=f[q[hd]]+sum[i-2]-sum[q[hd]]+a[i]+a[i-1];
while(hd<=tl&&f[q[tl]]-sum[q[tl]]<f[i-1]-sum[i-1])--tl;
q[++tl]=i-1;
}
for(int i=1;i<=n;++i)ans=max(ans,sum[min(i+k-1,n)]-sum[i]+f[i]);
printf("%lld",max(ans,sum[k]));
return 0;
}
最新文章
- vmware 下centos7配置网络
- java弱引用之WeakHashMap相关资料
- 洛谷P2434 [SDOI2005]区间
- Leetcode: Remove K Digits
- [开发笔记]-jQuery获取checkbox选中项等操作及注意事项
- php通过正则从字符串中获取所有图片url地址
- 每天一个小算法(4)----在O(1)时间删除指定结点
- linux账户管理(centos)
- Delphi - XP扫雷外挂制作
- hdu 4284 Travel(floyd + TSP)
- Win10更新补丁失败后出现无法更新正在撤销 解决办法
- git基本使用(搭建Git服务器)
- javascript中的事件类型
- Java将数据按列写入Excel并设置格式(字体、背景色、自动列宽、对齐方式等)
- Laravel从入门到精通
- liunx tomcat 运行模式apr
- lua -- 在弹框中显示物品列表
- Vue2.0,Express实现的简单跨域
- 【xsy1012】KSHKM的基因工程 AC自动机DP
- (NGUI)UISprite 切换图集