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

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

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

当然要求关啦。