luogu2627 修剪草坪
2024-09-04 10:42:26
dp[i]表示1~i最大效率
记一下前缀和
转移就是f[i]=max(f[i],f[j-1]-sum[j])+sum[i] (i-k<=j<=i)
发现括号里的只与j有关 开一个单调队列维护一下
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
//#pragma GCC optimize ("O3")
int n,k;
ll e[];
ll dp[];
ll sum[];
ll q[],head,tail;
ll num[];
long long calc(int a)
{
num[a]=dp[a-]-sum[a];
while(head<=tail && num[q[tail]]<num[a])tail--;
q[++tail]=a;
while(head<=tail && q[head]<a-k)head++;
return num[q[head]];
}
//f[i]=max(f[i],f[j-1]-sum[j])+sum[i] (j 1~e)
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++){scanf("%lld",&e[i]);sum[i]=sum[i-]+e[i];}
for(int i=;i<=n;i++)dp[i]=calc(i)+sum[i];
cout<<dp[n];
}
最新文章
- BZOJ 1858 线段树
- 静态内容生成器&mdash;&mdash;Wyam
- 64位Win7下运行ASP+Access网站的方法
- iOS应用IAP设置总结
- Pre-Update and Pre-Insert Trigger Examples For Oracle Forms
- [HDOJ5763]Another Meaning(KMP, DP)
- SQL Server 修复数据库 相关 脚本 之 DBCC CHECKDB 用法 来自同事分享
- 实现类似QQ的即时通信程序(十一)
- java_method_正则校验
- YUI的UA检测
- javaWeb学习总结(10)- EL函数库(2)
- 简单使用redis实现sso单点登录
- 1003: [ZJOI2006]物流运输 = DP+SBFA
- META-INF文件夹中的MANIFEST.MF 的作用
- C语言截取从某位置开始指定长度子字符串方法
- [js]js设计模式-工厂模式
- swift类型擦除的定义-swift的类型擦除只是一个类型高低阶转换的游戏。
- 【转载】Exchange 2010配置与安装实用手册
- mysql 数字类型的长度区别
- HTTP协议图--HTTP 工作过程
热门文章
- C语言基础知识【存储类】
- Pycharm 中错误ImportError: No module named appium
- z-index随笔
- [转]Html position(static、relative、absolute、fixed)
- vue路由vue-route
- wxwidget自定义消息处理步骤
- UnicodeEncodeError: &#39;latin-1&#39; codec can&#39;t encode characters in position 0-3: ordinal not in range(256)
- Python菜鸟之路:Python基础-Socket基础-1
- android 获取短信验证码倒计时
- CentOS iSCSI服务器搭建------Initiator篇