P2627修剪草坪题解

状态：设f[i][0]表示以i结尾但不取i的最大连续字段和,f[i][1]表示要取i的最大值，因此，有方程f[i][0]=max(f[i-1][0],f[i-1][1])(f[i][0]可由f[i-1]直接推过来)

f[i][1]=max(f[j][0]+sum[i]-sum[j])(i-k+1<=j+1<=i)即由j+1作为区间的左端点

可变形为f[i][1]=max(f[j][0]-sum[j])+sum[i];

于是可设置一个单调队列，

f[q[head]][0]-sum[q[head]]要最大，

因为我们是拿队首去跟i比，而队首实际上就是区间左端点

维护时只需保证区间长度与head与tail的关系即可

#include<bits/stdc++.h>
using namespace std;

const int maxn=100005;
long long a[maxn],sum[maxn],f[maxn][2],q[maxn],n,k;
long long head,tail;

int main()
{
    scanf("%lld%lld",&n,&k);
    head=tail=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)
    {
        f[i][0]=max(f[i-1][0],f[i-1][1]);
        while(q[head]<i-k&&head<=tail) head++;
        f[i][1]=f[q[head]][0]-sum[q[head]]+sum[i];
        while(f[i][0]-sum[i]>f[q[tail]][0]-sum[q[tail]]&&head<=tail) tail--;
        q[++tail]=i;
    }
    printf("%lld",max(f[n][0],f[n][1]));
    return 0;
}