题目描述

给出一个数列，每次会从数列中挑选出一个数字，但规则是每次只能选和0相邻的数字（不能选0），拿走一个数字后，将这个数字变成0。 现有两个玩家都采取最优策略，使自己最后获得数字的和为最大值，输出最后两位玩家的得分，优胜者将获得参观航天发射基地的门票。保证这个数列初始时至少有一个数字为0。

输入说明

第一行，一个正整数N(N < 1000000) 。第二行为N个整数，用一个空格分隔，N个整数和不超过2^64-1。

输出说明

输出数据是一行，包括两个整数，用一个空格分隔，表示两人最后的得分。

输入样例

8

1 2 0 3 7 4 0 9

输出样例

17 9

本题 只讨论让选手得到尽量多的石子。

由于双方最终石子数之和是确定的,双方的目标就是使自己-别人的石子数差最大化。

首先我们可以抽象问题:

有两个栈,若干个双头队列,总长度不超过10^6

每次可以从栈顶取一个数,也可以从双头队列选一端取一个数。

2人轮流以最大化自己数字和的目标取数,问最终结果。

如果只有一个栈,那么取法是一定的。

如果只有一个队列,如果是奇数个数据,取法也是一定的。如果是偶数个,先手会取

max(奇数位的和,偶数位的和).

本题的关键难点是将原始数据简化成类似下面的数据。即可取元素都是递减的,比如

1 2 3 0 2 1 2 0 4 1

这里：中间没有凸状数据，两头没有凹状数据，类似

1<2,   4>1.

容易发现先手只要贪心地从能取的元素里面拣最大的取走即可。由于每次一定可以取全场最大值,所以只要一次排序然后交替取值即可。

4 3 2 2 2 1 1 1

如果中间有凸状数据，或者两头有凹状数据,我们可以通过 2 个操作来化简数列:

1. 如果两头有凹状数据，即最左端是 A B.. 或者最右端是..B A, 且 A>=B，

那么双方在有其它方案时都不会愿意先取走 B,故这种情况可以留到博弈的最后。

由于石子数是确定的,可以直接推出最后谁取到了 A,算出相应差值。

由于可以留到游戏的最后,此时删除这两堆并不影响两人之前的决策。

2. 如果中间有凸状数据，即有一段 ..A B C.. 且满足 B>=A B>=C，那么我们直接把 ABC 替换成一个 A+C-B 即可。

我们可以这样想:选 A,B,C 的时候是因为没有更好的决策而被迫选的。事实上当全场没有大于 A+C-B 的石子堆可以直接取时,才会考虑取 A,C 中的一个。那么不管第一次取 A,B,C 中的元素是从哪边,

后手选 B>A(C) 一定是最好的选项。 故先手一定取走 A+C,后手取走 B。从对分数差的贡献来看,我们可以直接把 A,B,C 代替成 A+C-B