自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:57:25，当前版本为作者最后更新于2024-04-28 17:27:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先有个比较显然的 dp。设 $dp_i$ 为从 $i$ 开始开到 $n$ 的最大金币数量，显然有：

$$dp_i=\max(a_i,\max_{1\le j\le a_i}dp_{i+j}+\sum^{j-1}_{k=1}a_{i+k}) $$

含义是枚举拿不拿 $a_i$ 和开完之后拿多少个。这是 $O(n^2)$ 的所以考虑优化，拆开式子后，发现一次转移等价于：

• $i+1\sim i+a_i$ 区间查询最大值。
• $i+1\sim n$ 区间加 $a_i$。
• $i$ 单点加 $dp_i$。

上个线段树即可，复杂度 $O(n\log n)$。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

struct node {
	int l, r; ll v, add;
} t[MAXN << 2];

inline 
void upd(int p, ll v) {
	t[p].add += v, t[p].v += v;
}

inline 
void pushup(int p) {
	t[p].v = max(t[p << 1].v, t[p << 1 | 1].v);
}

inline 
void pushdown(int p) {
	if (!t[p].add) return ;
	upd(p << 1, t[p].add), upd(p << 1 | 1, t[p].add), t[p].add = 0;
}

void build(int l, int r, int p) {
	if (l > r) return ;
	t[p].l = l, t[p].r = r, t[p].v = t[p].add = 0;
	if (l == r) return ; int mid = l + r >> 1;
	build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
}

void modify(int l, int r, ll v, int p) {
	if (l > r) return ;
	if (l <= t[p].l && t[p].r <= r) return upd(p, v);
	pushdown(p); int mid = t[p].l + t[p].r >> 1;
	if (l <= mid) modify(l, r, v, p << 1);
	if (r > mid) modify(l, r, v, p << 1 | 1); pushup(p);
}

ll query(int l, int r, int p) {
	if (l > r) return 0;
	if (l <= t[p].l && t[p].r <= r) return t[p].v;
	pushdown(p); int mid = t[p].l + t[p].r >> 1; ll res = 0;
	if (l <= mid) res = max(res, query(l, r, p << 1));
	if (r > mid) res = max(res, query(l, r, p << 1 | 1)); return res;
}

int T, n; ll a[MAXN], dp[MAXN];

int main() {
    for (scanf("%d", &T); T--;) {
	    scanf("%d", &n), build(1, n, 1);
	    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	    for (int i = n, l, r; i; i--) {
	    	dp[i] = a[i], l = i + 1, r = min<ll>(i + a[i], n);
	    	dp[i] = max(dp[i], query(l, r, 1));
	    	modify(l, n, a[i], 1), modify(i, i, dp[i], 1);
		}
		printf("%lld\n", dp[1]);
	}
}