题面

点击此处前往原题。

在一年前赢得了小镇的最佳草坪比赛后，Farm John变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farm John希望能够再次夺冠。

然而，Farm John的草坪非常脏乱，因此，Farm John只能够让他的奶牛来完成这项工作。Farm John有$n\in [1,10^5]\bigcap\mathbb{N^*}$只排成一排的奶牛。每只奶牛的效率是不同的，第$i$只奶牛的效率为$e_i\in [1,10^9]\bigcap\mathbb{N^*}$。

靠近的奶牛们很熟悉，因此，如果Farm John安排超过$k$只连续的奶牛，那么，这些奶牛就会罢工去开派对。因此，现在Farm John需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过$k$只奶牛。

题解

考虑直接进行规划比较麻烦，那么考虑将一些奶牛移除以防止她们开派对。

配合单调队列即可搞定。

代码

#include <bits/stdc++.h>
using namespace std;
const unsigned int MAXN = 100002;
long long i, j, k, n, m, f[MAXN], a[MAXN], q[MAXN];
int main() {
    long long sum = 0;
    cin >> n >> k;
    for ( i = 1; i <= n; i++ ) {
        cin >> a[i];
        sum += a[i];
    }
    int left = 1, right = 1;
    for ( i = 1; i <= n; i++ ) {
        while ( left <= right && i - q[left] > k + 1 )
            left++;
        f[i] = a[i] + f[q[left]];
        while ( left <= right && f[q[right]] >= f[i] )
            right--;
        q[++right] = i;
    }
    for ( i = n - k; i < n; i++ ) {
        f[i + 1] = min( f[i + 1], f[i] );
    }
    cout << sum - f[n] << endl;
    return 0;
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/861.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。