题目详情
返回题库题目描述
来自USACO 2024 December Contest, Silver
Bessie 和 Elsie 发现了一行N个蛋糕（$ 2 \leq N \leq 5 \times 10^5 $，N为偶数），大小依次为$ a_1,a_2, \dots , a_N $（$ 1 \leq a_i \leq 10^9 $）。
两头奶牛都想吃到尽可能多的蛋糕。但是，作为非常文明的奶牛，她们决定玩一个游戏来分割蛋糕！游戏在两头奶牛之间轮流进行回合。每个回合进行以下两者之一：
- Bessie 选择两个相邻的蛋糕并将它们堆叠起来，制造大小为两者大小之和的一个新蛋糕。
- Elsie 选择最左边或最右边的蛋糕藏起来。
当只剩下一个蛋糕时，Bessie 吃掉它，而 Elsie 吃掉她藏起来的所有蛋糕。如果两头奶牛都采取最优策略以最大化她们吃到的蛋糕量，并且 Bessie 先进行回合，那么每头奶牛将会吃到多少蛋糕？
输入描述
每个测试点包含T（$ 1 \leq T \leq 10 $）个独立的测试用例。输入保证一个测试点中的所有N之和不超过$ 10^6 $。
每个测试用例的格式如下。第一行包含N。下一行包含N个空格分隔的整数$ a_1,a_2, \dots , a_N $
数据范围：
- 测试点 2：所有 $ a_i $ 相等。
- 测试点 3：$ N \leq 10 $。
- 测试点 4-7：$ N \leq 5000 $。
- 测试点 8-11：没有额外限制。
输出描述
对于每个测试用例，输出一行，包含b和e，表示 Bessie 和 Elsie 在两头奶牛都采取最优策略的情况下分别吃到的蛋糕量。
提示
对于第一个测试用例，在最优策略下，
- Bessie 将堆叠中间两个蛋糕。现在蛋糕的大小为[40,50,10]
- Elsie 将吃掉最左边的蛋糕。现在剩余的蛋糕的大小为[50,10]
- Bessie 堆叠剩余的两个蛋糕。
Bessie 将吃到30+20+10=60的蛋糕，而 Elsie 将吃到40的蛋糕。
第二个测试用例是第一个测试用例反转的情况，因此答案相同。