Cake Game

题目描述

Bessie 和 Elsie 发现了一排 $N$ 个蛋糕（$2 \leq N \leq 5\cdot 10^5, N \text{ even}$），按顺序大小分别为 $a_1,a_2,\dots,a_N$（$1\le a_i\le 10^9$）。 每头奶牛都想吃到尽可能多的蛋糕。然而，作为很文明的奶牛，她们决定通过玩一个游戏来分配蛋糕！游戏过程中两头奶牛轮流行动。每一回合由以下之一组成： Bessie 选择两个相邻的蛋糕并将它们叠在一起，形成一个新的蛋糕，其大小为两者大小之和。 Elsie 选择最左端或最右端的一个蛋糕，并把它放入她的储藏中。 当只剩下一个蛋糕时，Bessie 吃掉它，而 Elsie 吃掉她储藏中的所有蛋糕。如果两头奶牛都以最大化自己吃到的蛋糕量为目标并采取最优策略，且 Bessie 先手，那么每头奶牛分别会吃到多少蛋糕？

输入格式

每个输入包含 $T$（$1\le T\le 10$）个相互独立的测试用例。保证一个输入中所有测试用例的 $N$ 之和不超过 $10^6$。 每个测试用例如下格式：第一行包含 $N$。下一行包含 $N$ 个用空格分隔的整数 $a_1,a_2,\ldots,a_N$。

输出格式

对于每个测试用例，输出一行，包含 $b$ 和 $e$，分别表示在双方都采取最优策略时，Bessie 和 Elsie 各自会吃到的蛋糕总量。

2
4
40 30 20 10
4
10 20 30 40

60 40
60 40

提示

对于第一个测试用例，在最优策略下， Bessie 会将中间两个蛋糕叠在一起。此时蛋糕大小为 $[40,50,10]$。 Elsie 会吃掉最左端的蛋糕。剩余蛋糕大小为 $[50,10]$。 Bessie 将剩下的两个蛋糕叠在一起。 Bessie 将吃到 $30+20+10=60$ 的蛋糕，而 Elsie 将吃到 $40$ 的蛋糕。 第二个测试用例是第一个的逆序，因此答案相同。 SCORING: Input 2: 所有 $a_i$ 都相等。 Input 3: $N\le 10$ Inputs 4-7: $N\le 5000$ Inputs 8-11: 无额外限制。 Problem credits: Linda Zhao, Agastya Goel, Gavin Ye

标签: USACO|2024|Silver

来源

USACO|2024|Silver