思路：
单调队列+dp；
然而劳资不会单调队列，所以，线段树水过;
来，上代码：
#include#include #include #include using namespace std;#define maxn 200005struct TreeNodeType { int l,r,dis,mid;};struct TreeNodeType tree[maxn<<2];int n,lit,rit,ai[maxn];inline void in(int &now){ int if_z=1;now=0; char Cget=getchar(); while(Cget>'9'||Cget<'0') { if(Cget=='-') if_z=-1; Cget=getchar(); } while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } now*=if_z;}inline void tree_build(int now,int l,int r){ tree[now].l=l,tree[now].r=r; if(l==r) { in(tree[now].dis); return ; } tree[now].mid=l+r>>1; tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r); tree[now].dis=max(tree[now<<1].dis,tree[now<<1|1].dis);}int tree_query(int now,int l,int r){ if(tree[now].l==l&&tree[now].r==r) return tree[now].dis; if(l>tree[now].mid) return tree_query(now<<1|1,l,r); else if(r<=tree[now].mid) return tree_query(now<<1,l,r); else return max(tree_query(now<<1,l,tree[now].mid),tree_query(now<<1|1,tree[now].mid+1,r));}void tree_add(int now,int to,int x){ if(tree[now].l==tree[now].r) { tree[now].dis+=x; return ; } if(to<=tree[now].mid) tree_add(now<<1,to,x); else tree_add(now<<1|1,to,x); tree[now].dis=max(tree[now<<1].dis,tree[now<<1|1].dis);}int main(){ in(n),in(lit),in(rit); tree_build(1,0,n); for(int i=lit+1;i<=n;i++) { int l=i-rit,r=i-lit; if(r>=lit) tree_add(1,i,tree_query(1,max(l,lit),r)); } cout<