本文主要是介绍BZOJ 2442 [Usaco2011 Open]修剪草坪 DP+单调队列优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，
新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。
然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N
(1 <= N <= 100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，
奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。
靠近的奶牛们很熟悉，因此，如果FJ安排超过K只连续的奶牛，那么，这些奶牛就会罢工
去开派对:)。因此，现在FJ需要你的帮助，计算FJ可以得到的最大效率，并且该方案中
没有连续的超过K只奶牛。
Input
* 第一行：空格隔开的两个整数N和K
* 第二到N+1行：第i+1行有一个整数E_i
Output
* 第一行：一个值，表示FJ可以得到的最大的效率值。
Sample Input
5 2
1
2
3
4
5
输入解释：
FJ有5只奶牛，他们的效率为1，2，3，4，5。他们希望选取效率总和最大的奶牛，但是
他不能选取超过2只连续的奶牛
1
2
3
4
5
输入解释：
FJ有5只奶牛，他们的效率为1，2，3，4，5。他们希望选取效率总和最大的奶牛，但是
他不能选取超过2只连续的奶牛
Sample Output
12
FJ可以选择出了第三只以外的其他奶牛，总的效率为1+2+4+5=12。
HINT
传送门
直接求解原问题比较麻烦，
连续K个不好弄，，
那就可以看作去掉了几个值，
使得这些去掉的位置差距不超过K，
而且和最小。
然后答案就是总和减一下就好了。
那么就是一个灰常简单的DP……
用f[u]表示到了u位置的最小和，
那么f[u]=min(f[v])+num[u]
num[u]是u上的值，而v我们通过一个枚举得到：
v--> (u-1)~(u-K) //可能有些细节方面的问题，但是不必在意到时候注意就好
那么直接枚举的话就是O(N*K)的DP。
显然是可以简单地用单调队列来优化的。
时间复杂度O(N)。
普及的时候码过的……
直接就贴p的代码了（懒）
反正可读性都一样。
var a,f,q:array[0..100005] of int64;n,m,i,j,head,tail,temp:longint;sum,ans:int64;
beginreadln(n,m);sum:=0; ans:=0;for i:=1 to n dobeginreadln(temp);a[i]:=temp;sum:=sum+a[i];end;fillchar(f,sizeof(f),$7f);for i:=1 to m do q[i+1]:=i;head:=0; tail:=m+1;f[0]:=0;for i:=1 to n dobeginwhile (head<tail)and(q[head]<i-m-1) do inc(head);f[i]:=f[q[head]]+a[i];inc(tail);q[tail]:=i;while (head<tail)and(f[q[tail]]<=f[q[tail-1]]) dobegindec(tail);q[tail]:=q[tail+1];end;end;for i:=n-m to n doif sum-f[i]>ans then ans:=sum-f[i];writeln(ans);
end.这篇关于BZOJ 2442 [Usaco2011 Open]修剪草坪 DP+单调队列优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
