4453. game

【题目背景】

艾莉丝和抱朴正在做游戏。

【题目描述】

一行有 $n$ 个正整数 $a_i$。Alice 和 Bob 将在这上面做游戏，保证 $n$ 为偶数。

游戏进行若干轮，每一轮双方都要进行如下操作：

1. Alice 将两个相邻的数 $a,b$ 合并起来，并在原来的位置放一个为 $a+b$ 的数取代 $a,b$ 两个数。

2. Bob 选择最左边或者最右边的数，加入到自己的分数中。

特别的，当进行玩一轮操作后，如果只剩下一个数，则这个数就是 Alice 的分数。

Alice 和 Bob 都想要最大化自己的分数，在两个人足够聪明的情况下，他们的分数会是多少？

【输入格式】

本题有多组测试数据。

第一行一个正整数 $T$ 表示测试点编号和数据组数。每组测试数据的输入格式如下。

第一行一个正整数 $n$，表示初始的数组个数。

接下来一行 $n$ 个正整数，表示初始的数列 $a$。

【输出格式】

输出 $T$ 行，对于每一行测试数据，一行两个正整数，分别表示最优策略下 Alice 和 Bob 的分数。

【样例输入】

2
4
40 30 20 10
4
10 20 30 40

【样例输出】

60 40
60 40

【样例说明】

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

Alice 将堆叠中间两个蛋糕。现在蛋糕的大小为 $[40,50,10]$。

Bob 将吃掉最左边的蛋糕。现在剩余的蛋糕的大小为 $[50,10]$。

Alice 堆叠剩余的两个蛋糕。

Alice 将吃到 $30+20+10=60$ 的蛋糕，而 Bob 将吃到 $40$ 的蛋糕。

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

大样例。

【数据规模与约定】

【来源】

在此键入。