bzoj#P3493. PA2010 Termites
PA2010 Termites
题面描述
有两个玩家,会去挑选一些数字,每次只能选至少与一个 相邻的数字(不能选 ),拿完一个数字后这个数字会变成 。
两个玩家都采取最优策略,使自己拿到的数字的和最大,问最后两位玩家的得分。
输入格式
第一行一个正整数 , 表示数字的数量
第二行 个整数, 为给定的数字
输出格式
两个整数, 分别为最后两位玩家的得分.
样例输入
8
1 2 0 3 7 4 0 9
样例输出
17 9
样例解释
Explanation of the example: The fence consisted of 8 planks, out of which 2 have already been eaten. The first termite in his first turn can choose between planks of heights 2, 3, 4 and 9. During the optimal game, in the consecutive turns, termites will eat planks of heights 9, 2, 1, 4, 7 and 3.
数据范围
对于所有的数据, 满足 . 保证初始时至少有一个 .