题面

点击此处前往原题

在一年前赢得了小镇的最佳草坪比赛后,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;
}
Last modification:February 19th, 2021 at 01:50 pm
如果您觉得我的文章有用,给颗糖糖吧~