传送门

这题的DP真是刷新了我的理解,竟然还要用队列优化。。。。

 #include<iostream>
#include<cstdio>
using namespace std;
long long ans1=;
long long ans,n,k;
const int maxn=1e5+;
long long a[maxn],f[maxn],q[maxn];
inline int read()
{
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
int main()
{
n=read();
k=read();
if(n==)
{
cout<<<<endl;
return ;
}
for(int i=;i<=n;i++)
{
a[i]=read();
ans=ans+a[i];
}
int l=,r=;
for(int i=;i<=n;i++)
{
while(l<=r&&f[q[r]]>=f[i-])
{
r--;
}
q[++r]=i-;
while(l<=r&&q[l]<i-k-)
{
l++;
}
f[i]=f[q[l]]+a[i];
}
for(int i=n-k;i<=n;i++)
{
ans1=min(ans1,f[i]);
}
printf("%lld",ans-ans1);
return ;
}

最新文章

  1. sscanf格式化输出
  2. Force.com平台基础--前言
  3. Convert Sorted Array to Binary Search Tree With Minimal Height
  4. linux 安装redis
  5. 安卓接入ShareSDK问题
  6. 转:QT 的点点滴滴 错误总结
  7. javascript一些常用函数
  8. [Google Code Jam (Qualification Round 2014) ] A. Magic Trick
  9. HDOJ 1423 Greatest Common Increasing Subsequence(dp)
  10. 剑指Offer——携程笔试题+知识点总结
  11. 2018蓝桥杯 省赛B题(明码)
  12. Loadrunner11的安装方法和破解
  13. locked (a oracle.jdbc.driver.T4CConnection
  14. 20155225 2016-2017-2 《Java程序设计》第五周学习总结
  15. 1009 Product of Polynomials (25 分)
  16. Web前端的状态管理
  17. Django html标签make_safe
  18. uoj 67 新年的毒瘤 tarjan求割点
  19. Python 创建元组tuple
  20. HTTP缓存机制--客户端缓存(转)

热门文章

  1. Mysql数据类型TINYINT(1)与BOOLEAN踩坑记
  2. Java字段初始化规律
  3. net core WebApi——使用NPOI导入导出操作
  4. 网络编程java
  5. Spring基础(二)
  6. Nmon监控结果分析
  7. Ubuntu18.04 安装 OpenCV 4.1.1
  8. Ceph Paxos相关代码解析
  9. 富文本编辑器(wangEditor)
  10. ssd原理及代码实现详解