洛谷2627 修剪草坪

双倍经验：洛谷2034 选择数字

题意

从一个数列中选出一些数，要求不能有超过 $k$ 个连续的数，求这些数的最大和。

数列长度 $N\le 100000$ 。

题解

令 $f[i]$ 表示前 $i$ 个数的最优解，$sum[i]$ 表示前缀和，转移方程式为：

$$f[i] = \max_{j=i-k}^i f[j-1] + sum[i] - sum[j]$$

$$f[i] = \max_{j=i-k}^i \{f[j-1] - sum[j]\} + sum[i]$$

显然可以用单调队列优化。

upd 20190912: $j$ 可以取到 $i$ ，所以应该先把 $i$ 入队后再算。代码已更新。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

deque <ll> q;
ll n,k,s[100005],f[100005],cur[100005];

signed main()
{
    n=read(); k=read();
    for (ll i=1;i<=n;i++) s[i]=s[i-1]+read();
    q.emplace_back(0);
    for (ll i=1;i<=n;i++)
    {
        cur[i]=f[i-1]-s[i];
        while (!q.empty() && q.front()<i-k) q.pop_front();
        while (!q.empty() && cur[q.back()]<=cur[i]) q.pop_back();
        q.emplace_back(i);
        f[i]=s[i]+cur[q.front()];
    }
    return !printf("%lld",f[n]);
}