After winning the annual town competition for best lawn a year ago,Farmer John has grown lazy; he has not mowed the lawn since then and thus his lawn has become unruly. However, the competition is once again coming soon, and FJ would like to get his lawn into tiptop shape so that he can claim the title.

Unfortunately, FJ has realized that his lawn is so unkempt that he will need to get some of his N (1 <= N <= 100,000) cows, who are lined up in a row and conveniently numbered 1..N, to help him. Some cows are more efficient than others at mowing the lawn; cow i has efficiency E_i (0 <= E_i <= 1,000,000,000).

FJ has noticed that cows near each other in line often know each other well; he has also discovered that if he chooses more than K (1 <= K <= N) consecutive (adjacent) cows to help him, they will ignore the lawn and start a party instead. Thus, FJ needs you to assist him: determine the largest total cow efficiency FJ can obtain without choosing more than K consecutive cows.

* Line 1: Two space-separated integers: N and K

* Lines 2..N+1: Line i+1 contains the single integer: E_i

* Line 1: A single integer that is the best total efficiency FJ can obtain.

5 2
1
2
3
4
5

12

INPUT DETAILS:

FJ has 5 cows whose efficiencies are 1, 2, 3, 4, and 5, in that order. He wants to choose some of the cows such that their total efficiency is maximized, but he cannot choose more than 2 consecutive cows.

OUTPUT DETAILS:

FJ chooses all cows but the third. The total efficiency of the cows is thus 1 + 2 + 4 + 5 = 12.

题目分析：

令f[i]表示选到第i个 并不选它的最小损失

所以 f[i]=min(f[j])+a[i] (i-k-1<=j<i)

拿单调队列搞一下就可以了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;
long long sum;
long long a[100100];
long long f[100100];
int q[100100];
int l=1,r;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i]),sum+=a[i];
    for(int i=1;i<=n;i++)
    {
        while(l<=r&&f[q[r]]>=f[i-1]) r--;
        while(l<=r&&q[l]<i-k-1) l++;
        f[i]=f[q[l]]+a[i];q[++r]=i-1;
    }
    long long ans=f[n];
    for(int i=n;i>=n-k;i--)
        ans=min(ans,f[i]);
    printf("%lld",sum-ans);
    return 0;
}