专栏文章

题解：B4168 [GXPC-S 2024] 分糖果

SSliarae
B4168题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miq7478n
此快照首次捕获于
2025/12/04 00:02
3 个月前
此快照最后确认于
2025/12/04 00:02
3 个月前
查看原文
设 fif_i 为考虑编号为 i∼ni \sim n 这段后缀的糖果，先手选能获得的最大收益。答案为 f1f_1。
考虑转移，假设要求 fif_i 且 f(i+1)∼nf_{(i + 1) \sim n} 已经求出。此时先手有两种决策，放弃这包糖果，获得下一轮的先手权，收益为 fi+1f_{i + 1}，或选这包糖果并获得 (i+1)∼n{(i + 1) \sim n} 这段后缀的后手收益。转移方程：
fi=max⁡(fi+1,∑j=inai−fi+1) f_{i} = \max(f_{i + 1}, \sum\limits_{j = i}^{n} a_i - f_{i + 1})
时间复杂度 O(n)O(n)。
CPP
#include <iostream>

using namespace std;
using LL = long long;

const int kN = 1e5 + 5;

int n;
int a[kN];

int main () {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	LL dp = 0, sum = 0; 
	for (int i = n; i; --i) 
		dp = max(dp, a[i] + sum - dp), sum += a[i];
	cout << dp << '\n';
	return 0; 
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...