自动搬运

查看原文

来自洛谷，原作者为

	CaoXian 这是我初一的成就，也是我最后的成就，几年学习终究是证明了自己的上限

搬运于2025-08-24 21:44:10，当前版本为作者最后更新于2022-06-25 09:55:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P2990 [USACO10OPEN]Cow Hopscotch G 题解

题意很简单，感觉可以使用动态规划求解。

先来看一个最暴力的 dp：

令 $dp_{i}$ 表示正着跳到第 i 个格子并且返回时跳到第 i - 1 个格子能得到的最大价值之和。

$$dp_{i} = v_{i} + v_{i - 1} + \max\limits_{\max(0, i - k) \leq j \leq i - 2}{\left\{dp_{j} + \sum\limits_{l = j + 1}^{i - 2}{\max(v_{l}, 0)}\right\}} $$

(感觉打得是不是有点复杂了)

应该挺好理解的，其中的 $v_{i} + v_{i - 1}$ 是将往回跳和正着跳踩到的格子的价值，$\sum\limits_{l = j + 1}^{i - 2}{\max(v_{l}, 0)}$ 表示去的时候可以踩的格子没有限制所以尽量把能踩到的权值为正的格子踩了。

可以发现，上面的 $\sum\limits_{l = j + 1}^{i - 2}{\max(v_{l}, 0)}$ 可以使用前缀和给优化掉。

所以就变成了：

$$dp_{i} = v_{i} + v_{i - 1} + \max\limits_{\max(0, i - k) \leq j \leq i - 2}{\left\{dp_{j} + sum_{i - 2} - sum_{j} \right\}} $$

其中：

$$sum_{i} = \sum\limits_{j = 1}^{i}{\max(v_{j}, 0)}$$

可以把 $\max\limits_{\max(0, i - k) \leq j \leq i - 2}{\left\{dp_{j} + sum_{i - 2} - sum_{j} \right\}}$ 里面的 $sum_{i - 2}$ 提出来，就变成了：

$$dp_{i} = v_{i} + v_{i - 1} + sum_{i - 2} + \max\limits_{\max(0, i - k) \leq j \leq i - 2}{\left\{dp_{j} - sum_{j} \right\}} $$

然后看到 $\max\limits_{\max(0, i - k) \leq j \leq i - 2}{\left\{dp_{j} - sum_{j} \right\}}$，其中 j 的取值范围的左右端点是随 i 的增加单调递增的，于是可以用一个单调递减的单调队列优化掉。

时间复杂度就是 $\Theta(n)$ 了。

最后的答案就是：

$$\max\left(\max\limits_{1 \leq i \leq n}{\left\{dp_{i} + sum_{\min(i + k - 1, n)} - sum_{i}\right\}}, sum_{k}\right) $$

注意 $dp_{1}$ 的初始值设为 $v_{1}$。

有什么不理解的可以问我 qwq。

Code:

#include <bits/stdc++.h>
#define re register
#define il inline
#define getchar gc
#define fu(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
il char gc() {static char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf; return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1000010, stdin), p1 == p2) ? -1 : *p1++;}
il void read(re ll& x) {x = 0; re int f = 1; re char ch = getchar(); while(ch < '0' || ch > '9') f *= ((ch == '-') ? -1 : 1), ch = getchar(); while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f;}
ll n, k, ans, front = 1, back, v[250001], sum[250001], dp[250001], q[250001];
int main() {
	read(n), read(k);
	fu(i, 1, n) read(v[i]), sum[i] = sum[i - 1] + max(v[i], 0ll);
	dp[1] = v[1];
	q[++back] = 0;
	fu(i, 2, n) {//dp 和 单调队列优化
		while(q[front] < i - k) ++front;
		if(front <= back) dp[i] = v[i] + v[i - 1] + dp[q[front]] + sum[i - 2] - sum[q[front]];
		while(front <= back && dp[i - 1] - sum[i - 1] >= dp[q[back]] - sum[q[back]]) --back;
		q[++back] = i - 1;
	}
	fu(i, 1, n) ans = max(ans, dp[i] + sum[min(n, i + k - 1)] - sum[i]);
	printf("%lld", max(ans, sum[k]));
	return 0;
}