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

Sliarae · 2025-02-21 22:59:33 · 题解

设 f_i 为考虑编号为 i \sim n 这段后缀的糖果，先手选能获得的最大收益。答案为 f_1。

考虑转移，假设要求 f_i 且 f_{(i + 1) \sim n} 已经求出。此时先手有两种决策，放弃这包糖果，获得下一轮的先手权，收益为 f_{i + 1}，或选这包糖果并获得 {(i + 1) \sim n} 这段后缀的后手收益。转移方程：

时间复杂度 O(n)。

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