Cake Game

题意

有一排偶数个蛋糕。Bessie 和 Elsie 轮流操作，Bessie 先手：

Bessie 每次选择相邻两个蛋糕，把它们合并成一个蛋糕；
Elsie 每次拿走最左边或最右边的一个蛋糕；
最后只剩一个蛋糕时，Bessie 吃掉它，Elsie 吃掉所有被她拿走的蛋糕。

两人都最优，求 Bessie 和 Elsie 最终分别吃到多少。

思路

先看一个小数据博弈暴力。Bessie 的回合枚举合并哪一对相邻蛋糕并取最大值，Elsie 的回合枚举拿左端或右端并取最小值。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:32
 * update_at: 2026-07-11 18:35
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

map<vector<ll>, ll> memo;

ll dfs_game(vector<ll> cakes) {
    if ((int)cakes.size() == 1) {
        return cakes[0];
    }

    if (memo.count(cakes) != 0) {
        return memo[cakes];
    }

    ll best;
    int len = cakes.size();

    if (len % 2 == 0) {
        // Bessie's turn：选择一对相邻蛋糕合并，最大化自己最后得到的蛋糕。
        best = -1;
        for (int i = 0; i + 1 < len; i++) {
            vector<ll> next_cakes;
            for (int j = 0; j < len; j++) {
                if (j == i) {
                    next_cakes.push_back(cakes[j] + cakes[j + 1]);
                    j++;
                } else {
                    next_cakes.push_back(cakes[j]);
                }
            }
            ll value = dfs_game(next_cakes);
            if (value > best) {
                best = value;
            }
        }
    } else {
        // Elsie's turn：拿走左端或右端，等价于最小化 Bessie 最后得到的蛋糕。
        best = (1LL << 62);

        vector<ll> left_removed;
        for (int i = 1; i < len; i++) {
            left_removed.push_back(cakes[i]);
        }
        best = min(best, dfs_game(left_removed));

        vector<ll> right_removed;
        for (int i = 0; i + 1 < len; i++) {
            right_removed.push_back(cakes[i]);
        }
        best = min(best, dfs_game(right_removed));
    }

    memo[cakes] = best;
    return best;
}

void solve_one_case() {
    int n;
    cin >> n;

    vector<ll> cakes;
    ll total = 0;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        cakes.push_back(x);
        total += x;
    }

    memo.clear();
    ll bessie = dfs_game(cakes);
    cout << bessie << ' ' << total - bessie << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_one_case();
    }

    return 0;
}

满分做法的关键是看清楚 Elsie 实际能拿走哪些初始蛋糕。

因为 N 是偶数：

Bessie 一共操作 $N/2$ 次；
Elsie 一共操作 $N/2-1$ 次。

Elsie 每次只能从当前两端拿蛋糕。她可以做到：从原始左端拿 l 个蛋糕，从原始右端拿 $N/2-1-l$ 个蛋糕。也就是说，Elsie 可以拿走任意一种“左边若干个 + 右边若干个”的组合，总数量固定为 $N/2-1$ 。

另一方面，Bessie 可以保护中间的一大块。她第一次合并中间两个蛋糕，之后 Elsie 如果拿走左端，Bessie 就把这个特殊大蛋糕向右合并；Elsie 如果拿走右端，Bessie 就把特殊大蛋糕向左合并。这样 Elsie 永远拿不到这个特殊蛋糕。

所以最终等价于：

Elsie 会拿走两端总共 $N/2-1$ 个初始蛋糕；
Bessie 会吃掉中间剩下的一个连续段；
这个连续段长度为：

N - (N/2 - 1) = N/2 + 1

Elsie 想让自己总和最大，也等价于让 Bessie 保留的连续段总和最小。

因此答案就是所有长度为 $N/2+1$ 的连续窗口中，窗口和的最小值。

用前缀和可以 $O(1)$ 求任意窗口和。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:32
 * update_at: 2026-07-11 18:35
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500005;

int n;
ll a[MAXN], prefix_sum[MAXN];

void solve_one_case() {
    cin >> n;
    prefix_sum[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix_sum[i] = prefix_sum[i - 1] + a[i];
    }

    int len = n / 2 + 1;
    ll bessie = (1LL << 62);

    // Bessie 最终保留一个长度为 n/2+1 的连续窗口，取其中最小的和。
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        ll sum = prefix_sum[r] - prefix_sum[l - 1];
        if (sum < bessie) {
            bessie = sum;
        }
    }

    ll total = prefix_sum[n];
    cout << bessie << ' ' << total - bessie << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_one_case();
    }

    return 0;
}

复杂度

每个测试用例只需要扫描一次数组和所有窗口。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题表面是博弈，核心却是把双方最优策略转成一个连续窗口问题。

Bessie 能保证最后吃到某个长度 $N/2+1$ 的连续段；Elsie 会让这个连续段尽量小，所以取最小窗口和即可。

目录

题意

思路

代码

复杂度

总结