题解 P1725 【琪露诺】

PiCaHor · 2018-02-09 19:43:58 · 题解

dp【i】表示i格的最大位置 维护一个不上升的队列， 存i-l——————i-r的最大 O（1） 查询 重载了比较

代码如下：：：：：： 没看懂私信

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstring> 
#include <queue>  
#define LL long long 
using namespace std;

struct node 
{
    LL id,c; 
    bool operator < (const node &a) const   
    {
        return a.c > c; 
    } 
}s; 

priority_queue <node> q; 
const int N=300020; 
int n,l,r,a[N]; 
LL ans,f[N];  

int main()
{
  scanf("%d%d%d",&n,&l,&r); 
  for(int i=0;i<=n;i++) 
  {
    scanf("%d",&a[i]); 
  }     
  s.id=0; s.c=0;  
  q.push(s); 
  for(int i=1;i<l;i++)  f[i]=0;  
  for(int i=l;i<=n+r;i++) 
  { 
    s.id=i-l; s.c=f[i-l]; 
    q.push(s); 
    while(q.top().id<i-r) q.pop(); 
    f[i]=q.top().c+a[i]; 
  }   
  for(int i=n+1;i<=n+r;i++) ans=max(ans,f[i]); 
  printf("%d\n",ans); 
  return 0;
}