记录编号	343749	评测结果	AAAAAAAAAA
题目名称	[USACO Open11] 修剪草坪	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.124 s
提交时间	2016-11-09 17:12:19	内存使用	3.34 MiB

#include <cstdio>
#include <cstring>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
#define MAXN 100002
long long dp[MAXN];
long long a[MAXN];
long long s[MAXN];
int q[MAXN<<1];
int main()
{
    freopen("mowlawn.in", "r", stdin);
    freopen("mowlawn.out", "w", stdout);
    int n, k;
    scanf("%d %d", &n, &k);
    long long sum = 0; 
    for(int i = 1; i <= n; i++)
        scanf("%lld", a+i);
    for(int i = 1; i <= n; i++)
        s[i] = s[i-1] + a[i];
    int head =0, tail = 0;
    for(int i = 1; i <= n; i++)dp[i] = a[i];
    for(int i = 1; i <= n; i++)
    {
        while(head < tail && q[head] < i-k-1)head++;
        dp[i] += dp[q[head]];
        while(head < tail && dp[q[tail]] >= dp[i])tail--;
        q[++tail] = i;
    }
    for(int i = n-k; i <= n; i++)
        dp[n] = min(dp[n], dp[i]);
    printf("%lld\n", s[n] - dp[n]);
    return 0;
}