我们可以考虑两种情况 区间之间不相重叠 和 重叠

f【i】【j】表示以当前最后一个区间以 i 结尾 并且选了 j 个区间

不相重叠的话 只要选 1-i-w 的max再加上 包含i在内的前四个数的和

相交的话 考虑因为可选的区间长度是固定的 所以我们可以考虑单调队列优化

sum维护的是前缀和

f【i】【j】=f【k】【j-1】+sum【i】-sum【k】

这样因为sum【i】是固定的 所以我们队列里维护的是f【k】【j-1】-sum【k】就好辣

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e4+,inf=0x3f3f3f3f;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,l,ans;
int sum[M],w[M],f[][M],mx;
int q[M],ql,qr,k;
int F(int x){return f[k-][x]-sum[x];}
int main(){
freopen("hard.in","r",stdin);
freopen("hard.out","w",stdout);
n=read(); m=read(); l=read();
for(int i=l;i<n+l;++i) w[i]=read();
n=n+*l-;
for(int i=;i<=n;++i) sum[i]=sum[i-]+w[i];
for(int i=;i<l;++i) f[][i]=-inf;
for(int i=l;i<=n;++i) f[][i]=sum[i]-sum[i-l];
for(k=;k<=m;++k){
ql=,qr=;
mx=-inf;
for(int i=;i<l;++i) f[k][i]=-inf;
for(int i=l;i<=n;++i){
while(ql<=qr&&q[ql]<=i-l) ++ql;
while(ql<=qr&&F(q[qr])<=F(i-)) --qr;
q[++qr]=i-;
mx=max(mx,f[k-][i-l]);
f[k][i]=max(mx+sum[i]-sum[i-l],F(q[ql])+sum[i]);
}
}
ans=;
for(int i=;i<=m;++i)
for(int j=l;j<=n;++j) ans=max(ans,f[i][j]);
printf("%d\n",ans);
return ;
}

最新文章

  1. bzoj2599: [IOI2011]Race(点分治)
  2. Redis模式匹配删除key
  3. 笔记:MAC OS X下配置PHP开发、调试环境
  4. iOS AFNetworking中cookie重定向
  5. php disk_free_space与disk_total_space实例介绍
  6. Shell基础整理
  7. canvas API ,通俗的canvas基础知识(四)
  8. VC6.0 error LNK2001: unresolved external symbol _main(转)
  9. csdn第四名
  10. oracle 树形SQL
  11. 288. Unique Word Abbreviation
  12. 延迟加载图片的 jQuery 插件:Lazy Load
  13. 返回canceled 代码 的原因
  14. Spring AOP (Spring 3.x 企业应用开发实战读书笔记第六章)
  15. WebAPI 用户认证防篡改实现HMAC(二)签名验证 AbsBaseAuthenticationAttribute--转
  16. C++类继承中的构造函数和析构函数 调用顺序
  17. P2P技术详解(二):P2P中的NAT穿越(打洞)方案详解
  18. java之Spring(IOC)装配Bean(手动装配、自动装配、注解装配)
  19. linux中的wc命令
  20. 设计模式---单一职责模式之桥模式(Bridge)

热门文章

  1. python -- sftp的方式下载终端文件
  2. 英文缩写SFR
  3. python-4函数式编程
  4. 笔记-爬虫-scrapy-srcapy-redis组件
  5. Java石头剪刀布小游戏
  6. Eclipse EE 运行 Myeclipse Web 应用
  7. laravel5.5表单验证
  8. 云计算之路-阿里云上:愚人节被阿里云OCS愚
  9. GTID环境中手动修复主从故障一例(Error 1146)
  10. (原)Unreal源码搬山-动画篇 自定义动画节点(一)