BZPRO

#2514. 取石子游戏

内存限制：128 MiB 时间限制：3 Sec
提交 提交记录 讨论

题目描述

A公司正在举办一个智力双人游戏比赛 --- 取石子游戏，游戏的获胜者将会获得A公司提供的丰厚的奖金，因此吸引了来自许多全国各地许多聪明的选手前来参加。
和经典的取石子游戏规则相比，A公司这次的取石子游戏规则复杂了很多：
l       总共有N堆石子依次排成一行，第i堆石子有ai个石子。
l       初始的时候有一些石子堆已经被A公司故意拿走。
l       两个玩家轮流来取石子，每次每个玩家可以取走一堆中的所有石子，但是有一个限制条件：一个玩家如果要取走一堆石子，必须这堆石子相邻的某一堆石子已经被取走(被某一个玩家取走或者初始的时候已经被拿走)。注意第1堆石子只和第2堆石子相邻，第N堆石子只和第N-1堆石子相邻，其余的第i堆石子与第i-1堆和第i+1堆石子相邻。
l       当所有石子都被取走，游戏结束。谁最后取得的总石子数最多，谁就获得了这场游戏的胜利。
作为这次比赛的参赛者之一，同样绝顶聪明的你，想知道对于任何一场比赛，如果先手
者和后手者都使用最优的策略，最后先手和后手分别能够取得的总石子数是多少。

输入格式

输入文件第一行是一个正整数N，表示石子的堆数。
第二行包含N个非负整数ai，分别表示每一堆石子的石子数，其中如果ai=0表示这一堆石子已经在最开始被A公司故意拿走。

输出格式

       输出文件只有一行，两个整数用空格隔开，分别表示在最优决策下先手能够取得的总石子数和后手能够取得的总石子数。

样例

样例输入


			
8

1 2 0 3 7 4 0 9

样例输出


			
 17 9

数据范围与提示

样例说明

       两个玩家在最优决策下取石子的顺序依次为9, 2, 1, 4, 7, 3，因此先手取得了9 + 1 + 7 = 17个石子，后手取得了2 + 4 + 3 = 9个石子。

数据范围

30%的数据中，2 ≤ N ≤ 100；。

100%的数据中，2 ≤ N ≤ 1,000,000，0 ≤ ai≤ 100,000,000，并且至少有一堆石子ai=0。

BZPRO Powered by Remmina.
Github Repository