【题解】P2627 [USACO11OPEN]Mowing the Lawn G
题面点击此处前往原题。在一年前赢得了小镇的最佳草坪比赛后，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; }