DP 方程:$f[i]=max(f[j])+v[i]$
转移范围:$i-r<=j<=i-l$
由此我们得知,每次只有 $[i-r,i-l]$ 部分的 $f$ 值对新更新的答案会有贡献. 故动态维护那个区间即可.
每次只会加入一个数,并弹出队首超出范围的数.
时间复杂度为 $O(n)$.
 
 Code:
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
const int maxn = 400000+3;
const long long inf = -1000000000;
int n,l,r, w[maxn];
long long d[maxn];
struct Node{
int pos;
long long val;
Node(int pos=0,long long val=0):pos(pos),val(val){}
};
deque<Node>Q;
inline void update(int cur)
{
while(!Q.empty() && Q.front().pos < cur )Q.pop_front();
}
inline void insert_x(Node a)
{
while(!Q.empty() && Q.front().val <= a.val)Q.pop_back();
Q.push_back(a);
}
int main(){
//freopen("in.txt","r",stdin);
long long ans = inf;
scanf("%d%d%d",&n,&l,&r);
for(int i =0;i <= n;++i)scanf("%d",&w[i]);
d[0] = w[0];
for(int i = 1;i<=n+l;++i){
int left = i-r, right = i-l;
if(right < 0) d[i] = inf;
else{
update(left);
insert_x(Node(right,d[right]));
d[i] =(long long) w[i] + Q.front().val;
if(i>n) ans = max(ans, d[i]);
}
}
printf("%lld",ans);
return 0;
}

  

最新文章

  1. 7.arm汇编 bic和orr指令
  2. codeforces 709D D. Recover the String(构造)
  3. vs 折叠跟展开所有方法。
  4. Android项目——电话拨号器
  5. uva193 - Graph Coloring
  6. 多线程爬虫Java调用wget下载文件,独立线程读取输出缓冲区
  7. 面试时遇到的SQL
  8. Jexus 配置多个站点
  9. [LeetCode141]Linked List Cycle
  10. href=&quot;#&quot; 的坑
  11. web Components 学习之路
  12. Linux查询进程和结束进程
  13. ssm项目导入activiti依赖后jsp页面el表达式报错
  14. HTML---仿网易新闻登录页
  15. OpenResty最佳实践
  16. pycaffe编译
  17. Angular 4 重定向路由
  18. 使用SignalR 2进行服务器广播
  19. JS的类型和值
  20. POj 1753--Flip Game(位运算+BFS)

热门文章

  1. asp.net--mvc--异步编程
  2. php表单常用正则表达式
  3. ELECTRON开发环境配置方法
  4. install pip 回顾
  5. request.getInputStream() 的两种解析方式
  6. ajax——dom基础
  7. 【树状数组】POJ 2155 Matrix
  8. SpringMVC中的 --- 异常处理
  9. Android中Calendar类的用法总结
  10. 通过学习Date和Calendar时写的日历