自动搬运

查看原文

来自洛谷，原作者为

	Nostopathy 壶关条件 https://www.luogu.me/article/moj9ohqn#，壶关私|吾与吾爱皆亡于高塔，君与君心皆存于盛夏

搬运于2025-08-24 21:17:31，当前版本为作者最后更新于2025-08-18 16:43:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

很明显这是一道 dp。

令 $dp_i$ 表示 $i \sim n$ 这段后缀中先手取能获得的最大收益。

为什么是后缀？从前往后推很难根据当前状态递推，考虑正难则反，从结果倒推开始的选择。

每个状态可选择：

• 把当前糖果给别人：保留上次状态，$dp_i=dp_{i+1}$；
• 把当前糖果给自己：获得这一段后缀的收益，$dp_i=sum-dp_{i+1}$，$sum$ 表示后缀和。

最后答案是 $dp_1$。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pb push_back
#define rep(a, b, c, d) for(int a=b; a<=c; a+=d)
const int N = 114514;
int n, a[N], dp[N];
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++ i)
		cin >> a[i];
	int s = 0;
	for(int i = n; i; -- i) {
		dp[i] = max(dp[i + 1], s + a[i] - dp[i + 1]);
		s += a[i];
	}
	cout << dp[1];
	return 0;
}

在这份代码的空间上，我们还可以做得更好。

看到 $dp_i$ 只用到上一步 $dp_{i+1}$，可用一个变量记录状态。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pb push_back
#define rep(a, b, c, d) for(int a=b; a<=c; a+=d)
const int N = 114514;
int n, a[N];
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++ i)
		cin >> a[i];
	int s = 0, f = 0;
	for(int i = n; i; -- i) {
		f = max(f, s + a[i] - f);
		s += a[i];
	}
	cout << f;
	return 0;
}

题解来之不易，麻烦留赞再走~

当然要求关啦。