修剪草坪（单调队列）

本文主要是介绍修剪草坪（单调队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

修剪草坪 (Standard IO)
时间限制: 1000 ms 空间限制: 262144 KB
Goto ProblemSet

题目描述

在一年前赢得了小镇的最佳草坪比赛后，约翰变得懒惰了，再也没有修剪过草坪。现在，新一轮的比赛又开始了，约翰希望能够再次夺冠。然而，约翰家的草坪非常脏乱，因此，约翰需要让他的奶牛来完成这项工作。约翰家有N头奶牛，排成一直线，编号为1到N。每只奶牛的能力是不同的，第i头奶牛的能力为Ei。靠在一起的奶牛很熟悉，所以如果安排相邻的K+1头奶牛一起工作，她们就会密谋罢工，所以不能选中连续的K+1头奶牛。因此，约翰需要你的帮助。如何挑选奶牛，才能使她们的能力之和最高呢？

输入

第一行：两个用空格隔开的整数：N和K，1≤ N≤ 100000，1≤ K≤ N
第二行到N+1行：第i+1行有一个整数，表示第i头牛的能力Ei，1≤ Ei <= 10^9

输出

第一行：单个整数，表示最大的能力之和

样例输入

5 2
1
2
3
4
5

样例输出

数据范围限制

对于30% 的数据，有1 ≤ n ≤ 10。
对于60% 的数据，有1 ≤ n ≤ 2, 000。
对于100% 的数据，有1 ≤ n≤ 100, 000。

提示

（除了第三头以外的所有奶牛都选，总能力为1+2+4+5=12）

正解

DP。（h2oDP）
设f1[i]为第i位为左端点的最大值。
设f2[i]为第i位为右端点的最大值。
f1[i]=MAX{f2[j]} {j<=i-2}
f2[i]=MAX{f1[j]+i~j区间和} {满足i-j+1<=k}
60分到手。
接下来，单调队列.
维护一个队列。队列是单调递减的，也就是说保证队头是最优的值。单调队列其实只有几个操作：
1、增加一个元素入队，入到队尾。就是将R+1；
2、将队尾元素提前。如果当前队尾的元素比上一个元素更优，那么上一个元素就没有存在感（没有用），就将它剔除。
3、删除无用的答案。如果队首的入队时间已经是很久以前了（入队后到现在的时间小于k）
4、更新DP答案。不用说了，怎么DP的怎么更新
所以，单调队列就维护完了。

代码

varn,k,l,r,maxn:int64;i,j:longint;a,q,f1,f2,z,max:array[-1..100000] of int64;
beginread(n,k);for i:=1 to n doread(a[i]);for i:=1 to n dobeginq[i]:=q[i-1]+a[i];end;l:=1;r:=0;for i:=1 to n dobeginf1[i]:=max[i-2];inc(r);z[r]:=i;while ((r>1) and (f1[z[r]]-q[z[r]-1]>=f1[z[r-1]]-q[z[r-1]-1])) dobegindec(r);z[r]:=z[r+1];z[r+1]:=0;end;if z[l]<i-k+1 theninc(l);if f2[i]<f1[z[l]]+q[i]-q[z[l]-1] thenf2[i]:=f1[z[l]]+q[i]-q[z[l]-1];if (f2[i]>max[i-1]) thenmax[i]:=f2[i]elsemax[i]:=max[i-1];end;for i:=1 to n doif maxn<f2[i] thenmaxn:=f2[i];writeln(maxn);
end.