BZOJ_2343_[Usaco2011 Open]修剪草坪 _单调队列_DP
题意：
N头牛，每头牛有一个权值，选择一些牛，要求连续的不能超过k个，求选择牛的权值和最大值
分析：
先考虑暴力DP，f[i] = f[j] + s[i]-s[j+1] (i-j-1<=k 1<=j<i)
意思是我们j+1不要，要j+2到i这部分
发现可以用单调队列优化一下
维护一个单调递减的单调队列，比较时用f[i]-s[i-1]比较
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
#define LL long long
int n,a[N],Q[N],l,r,k;
LL s[N],f[N],ans;
int main(){
scanf("%d%d",&n,&k);
int i;
for(i = 1;i <= n;i++){
scanf("%d",&a[i]);
s[i] = s[i - 1] + a[i];
}
r = 1;
for(i = 1;i <= k;i++){
f[i] = s[i];
while(l < r&& f[i] - s[i + 1] >= f[Q[r - 1]] - s[Q[r - 1] + 1]) r--;
Q[r++] = i;
ans = max(ans,f[i]);
}
for(i = k + 1;i <= n;i++){
while(l < r&& i - Q[l] - 1 > k) l++;
f[i] = f[Q[l]] - s[Q[l] + 1] + s[i];
while(l < r&& f[i] - s[i + 1] >= f[Q[r - 1]] - s[Q[r - 1] + 1]) r--;
Q[r++] = i;
ans = max(ans,f[i]);
// printf("%lld\n",f[i]);
}
printf("%lld\n",ans);
}