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可以得到的最大的效率值。
题解：
定义F[i]为前 i-1 只奶牛工作效率的最大值。
sum[i]是Ei的前缀和。
有F[i]=max{F[j]+sum[i-1]-sum[j]} (i-j<k)
可以用单调队列维护 F[j]-sum[j] 。
代码：
#include<cstdio>
using namespace std;
long long sum[100005];
long long f[100005];
long long n,k;
struct N{
int x;long long w;
N(int a=0,long long b=0){
x=a,w=b;
}
};
struct dddl{
int h,t;
N q[100005];
void insert(N a){
while(h!=t&&q[t-1].w<=a.w) t--;
q[t++]=a;
}
void pop(int x){
if(q[h].x==x) h++;
}
long long ask(){
return q[h].w;
}
}dddl;
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld",&sum[i]);
}
k++;
for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
dddl.insert(N(0,0));
for(int i=1;i<=n+1;i++){
dddl.pop(i-k-1);
f[i]=dddl.ask()+sum[i-1];
dddl.insert(N(i,f[i]-sum[i]));
}
printf("%lld\n",f[n+1]);
return 0;
}