记录编号	317919	评测结果	AAAAAAAAAA
题目名称	773.[USACO Open11] 修剪草坪	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.056 s
提交时间	2016-10-08 17:54:53	内存使用	1.82 MiB

#include<cstdio>
const int maxn=100005;
typedef long long ll;
int q[maxn];int head,tail;
int a[maxn];
ll f[maxn];//强制选第i个 
int main(){
    freopen("mowlawn.in","r",stdin);
    freopen("mowlawn.out","w",stdout);
    int n,k;scanf("%d%d",&n,&k);//连续k+1只必须选一只 
    ll sum=0;
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        sum+=a[i];
    }
    k++;
    q[tail++]=0;
    for(int i=1;i<=n;++i){
        while(head!=tail&&q[head]+k<i)head++;
        f[i]=f[q[head]]+a[i];
        while(head!=tail&&f[q[tail-1]]>=f[i])tail--;
        q[tail++]=i;   
    }
    ll ans=1ll<<60;
    for(int i=n-k+1;i<=n;++i){
        if(f[i]<ans)ans=f[i];
    }
    printf("%lld\n",sum-ans);
    fclose(stdin);fclose(stdout);
    return 0;
}