题解 P2627 【修剪草坪】

thmyl · 2017-09-09 15:02:09 · 题解

考虑动归，在第i点时，在i-k到i中肯定有一个点j不能选择，即：j为断点。

所以###f[i]=max(f[i],f[j-1]+a[j+1]+a[j+2]……a[i])（i-k<=j<=i）

所以维护前缀和，然后方程就变成了

f[i]=max(f[i],f[j-1]+sum[i]-sum[j]) (i-k<=j<=i)

变形一下变成：###f[i]=max(f[i],f[j-1]-sum[j])+sum[i] (i-k<=j<=i)

发现max里面的值只与j有关，所以可以用单调队列优化转移。

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,a[100010],sum[100010],f[100010];
long long d[100010];
int q[100010],head=0,tail=1;
long long que(int i){//让返回值尽量的大，队列单调减，使首元素恒最大 
    d[i]=f[i-1]-sum[i];
    while(head<=tail&&d[q[tail]]<d[i])tail--;
    q[++tail]=i;
    while(head<=tail&&q[head]<i-m)head++;
    return d[q[head]];
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)f[i]=que(i)+sum[i];
    cout<<f[n];
}