修剪草坪

https://loj.ac/problem/10177

题目描述

  每个奶牛有一定效率，不能安排编号连续超过\(k\)头奶牛，求最大效率。

思路

  比较容易设计出\(dp\)的状态，我们用\(f[i][0/1]\)表示前\(i\)头奶牛第\(i\)头奶牛选/不选获得的最大效率。那么\(f[i][0]=max\{f[i-1][0],f[i-1][1]\}\)，而\(f[i][1]=max\{\sum_{k=j}^{i}f[k][1]\}+a[i](i-m+1\le j\le i-1)\)，表示从\(j\)开始选连续的一段以\(i\)为右端点的区间的最大值，为了能去掉内层循环，我们可以用前缀和以及单调队列优化掉，这样复杂度为\(O(N)\)

代码

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

ll read()
{
    ll res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}
void write(ll x)
{
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

ll f[100010][2],sum[100010],q[100010],pos[100010];
int main()
{
    int n=read(),k=read(),x;
    for(int i=1;i<=n;i++)
        x=read(),sum[i]=sum[i-1]+x;
    int head=1,tail=1;
    for(int i=1;i<=n;i++)
    {
        f[i][0]=max(f[i-1][0],f[i-1][1]);
        while(head<=tail&&pos[head]<i-k)head++;
        f[i][1]=f[pos[head]][0]-sum[pos[head]]+sum[i];
        while(head<=tail&&f[pos[tail]][0]-q[tail]<=f[i][0]-sum[i])tail--;
        q[++tail]=sum[i];pos[tail]=i;
    }
    write(max(f[n][0],f[n][1]));
}