P2990 [USACO10OPEN]Cow Hopscotch G 题解

· · 题解

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;
}