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];
}

最新文章

  1. BZOJ 1858 线段树
  2. 静态内容生成器&mdash;&mdash;Wyam
  3. 64位Win7下运行ASP+Access网站的方法
  4. iOS应用IAP设置总结
  5. Pre-Update and Pre-Insert Trigger Examples For Oracle Forms
  6. [HDOJ5763]Another Meaning(KMP, DP)
  7. SQL Server 修复数据库 相关 脚本 之 DBCC CHECKDB 用法 来自同事分享
  8. 实现类似QQ的即时通信程序(十一)
  9. java_method_正则校验
  10. YUI的UA检测
  11. javaWeb学习总结(10)- EL函数库(2)
  12. 简单使用redis实现sso单点登录
  13. 1003: [ZJOI2006]物流运输 = DP+SBFA
  14. META-INF文件夹中的MANIFEST.MF 的作用
  15. C语言截取从某位置开始指定长度子字符串方法
  16. [js]js设计模式-工厂模式
  17. swift类型擦除的定义-swift的类型擦除只是一个类型高低阶转换的游戏。
  18. 【转载】Exchange 2010配置与安装实用手册
  19. mysql 数字类型的长度区别
  20. HTTP协议图--HTTP 工作过程

热门文章

  1. C语言基础知识【存储类】
  2. Pycharm 中错误ImportError: No module named appium
  3. z-index随笔
  4. [转]Html position(static、relative、absolute、fixed)
  5. vue路由vue-route
  6. wxwidget自定义消息处理步骤
  7. UnicodeEncodeError: &#39;latin-1&#39; codec can&#39;t encode characters in position 0-3: ordinal not in range(256)
  8. Python菜鸟之路:Python基础-Socket基础-1
  9. android 获取短信验证码倒计时
  10. CentOS iSCSI服务器搭建------Initiator篇