6118. 蛋糕游戏

贝茜和埃尔茜发现了一行 NN 个蛋糕（NN 为偶数），大小依次为 a1,a2,…,aNa1,a2,…,aN。

两头奶牛都想吃到尽可能多的蛋糕。

但是，作为非常文明的奶牛，她们决定玩一个游戏来分割蛋糕！

游戏在两头奶牛之间轮流进行回合。

每个回合进行以下两者之一：

1. 贝茜选择两个相邻的蛋糕并将它们堆叠起来，制造大小为两者大小之和的一个新蛋糕。
2. 埃尔茜选择最左边或最右边的蛋糕藏起来。

当只剩下一个蛋糕时，贝茜吃掉它，而埃尔茜吃掉她藏起来的所有蛋糕。

如果两头奶牛都采取最优策略以最大化她们吃到的蛋糕量，并且贝茜先进行回合，那么每头奶牛将会吃到多少蛋糕？

输入格式

每个测试点包含 TT 个独立的测试用例。

每个测试用例的格式如下。

第一行包含 NN。

下一行包含 NN 个空格分隔的整数 a1,a2,…,aNa1,a2,…,aN。

输出格式

对于每个测试用例，输出一行，包含 bb 和 ee，表示贝茜和埃尔茜在两头奶牛都采取最优策略的情况下分别吃到的蛋糕量。

数据范围

1≤T≤101≤T≤10,
2≤N≤5×1052≤N≤5×105,
1≤ai≤1091≤ai≤109,
输入保证一个测试点中的所有 NN 之和不超过 106106。

输入样例：

2
4
40 30 20 10
4
10 20 30 40

输出样例：

60 40
60 40

样例解释

对于第一个测试用例，在最优策略下，

1. 贝茜将堆叠中间两个蛋糕。现在蛋糕的大小为 [40,50,10][40,50,10]。
2. 埃尔茜将吃掉最左边的蛋糕。现在剩余的蛋糕的大小为 [50,10][50,10]。
3. 贝茜堆叠剩余的两个蛋糕。

贝茜将吃到 30+20+10=6030+20+10=60 的蛋糕，而埃尔茜将吃到 4040 的蛋糕。

第二个测试用例是第一个测试用例反转的情况，因此答案相同。

思路
本题要求解一个最优策略，举几个例子可以发现，每一步贝茜都要保证自己所拿的蛋糕不偏向两边，否则就会被埃尔茜拿走，因此两人的策略为：

1. 贝茜：第一次必须拿中间两个蛋糕，之后必须根据埃尔茜的选择，向反方向合并蛋糕，才能保证不会被埃尔茜拿走。
2. 埃尔茜从两边向中间拿蛋糕，使自己的蛋糕尽可能大。

我们可以发现，贝茜没得选择，埃尔茜可以找到一种最优方案。
因此，思路为：遍历埃尔茜的所有可能方案，找到最优方案，再求贝茜的。

一些细节
求埃尔茜拿走的蛋糕数(cnt)
因为贝茜先行动，举几个例子可以发现，贝茜拿走的蛋糕比埃尔茜多2个，可列式：cnt + cnt + 2 = n，解得cnt = (n - 2) / 2。
利用好前缀和，埃尔茜和贝茜的蛋糕总和都可用前缀和快速求出（结合注释理解）

import java.util.Scanner;public class Main {// 定义常量 Nstatic final int N = 500010;// 数组 a 表示第 i 个蛋糕的大小，s 表示前 i 个蛋糕的大小之和static long[] a = new long[N];static long[] s = new long[N];// ans1 表示贝茜拿走的蛋糕大小之和，ans2 表示埃尔茜拿走的蛋糕大小之和static long ans1, ans2;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取测试用例的数量 tint t = scanner.nextInt();while (t-- > 0) {// 初始化 ans1 和 ans2ans1 = 0;ans2 = 0;// 读取蛋糕的数量 nint n = scanner.nextInt();// 读取每个蛋糕的大小，并预处理前缀和for (int i = 1; i <= n; i++) {a[i] = scanner.nextLong();s[i] = s[i - 1] + a[i];}// 计算埃尔茜需要拿走的蛋糕数量int cnt = (n - 2) / 2;// 记录贝茜拿走的蛋糕范围int i = 1, j = n;// 枚举埃尔茜拿走的蛋糕的所有可能情况for (int k = 0; k <= cnt; k++) {// 从左边开始拿 k 个蛋糕，总和为 s[k]// 从右边开始拿 cnt - k 个蛋糕，总和为 s[n] - s[n - cnt + k]long sum = s[k] + s[n] - s[n - cnt + k];// 如果当前情况比之前的情况更优if (sum > ans2) {// 更新答案ans2 = sum;// 计算更新贝茜拿走的蛋糕范围i = k + 1;j = n - cnt + k;}}// 计算贝茜拿走的蛋糕大小之和ans1 = s[j] - s[i - 1];// 输出结果System.out.println(ans1 + " " + ans2);}scanner.close();}
}

import java.io.*;
import java.lang.*;
public class Main{public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));static int[] a = new int[500010];static long[] s = new long[500010];public static void main(String[] args) throws Exception{int T = Integer.parseInt(in.readLine());long res = 0;while(T-- > 0){int n = Integer.parseInt(in.readLine());String[] arr = in.readLine().split(" ");for(int i = 1; i <= n; i++){a[i] = Integer.parseInt(arr[i - 1]);s[i] = s[i - 1] + a[i];}res = s[n / 2 - 1];for(int i = n,j = n/2-2; i > n / 2 + 1; i--,j--){long t = s[n] - s[i-1] + s[n/2-1] - (s[n/2-1] - s[j]);res = Math.max(res, t);}out.write(s[n] - res + " "+ res + "\n");}in.close();out.close();}
}直接枚举两边的蛋糕，贝茜没得选，埃尔茜可以挑两边的蛋糕挑 n / 2 - 1 个，首先求左边n/2-1个前缀和，接着每次从左边减去一个蛋糕，右边加上一个蛋糕，枚举所有可能，求埃尔茜的最大蛋糕数量，接着拿着总蛋糕数减去埃尔茜最大蛋糕数即可