CHD-ACM CHDOJ 首页 题库 题单 比赛 评测 用户 讨论 帮助
工具
云剪贴板 树图画板 代码对比
登录 注册

4044: NOI2010湖北省选 二试 第1题 取石子游戏

时间限制：2000 ms 内存限制：512 MB
上传者：
提交：3 通过：3
提交提交记录讨论统计

题目描述

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

输入格式

第一行是一个正整数N，表示有多少堆石子。输入文件第二行是用空格隔开的N个非负整数a1, a2, …, aN，其中ai表示第i堆石子有多少个石子，ai = 0表示第i堆石子开始被A公司故意拿走。输入的数据保证0≤ai≤100,000,000，并且至少有一个i使得ai = 0。30%的数据满足2≤N≤100，100%的数据满足2≤N≤1,000,000。

输出格式

仅包含一行，为两个整数，分别表示都使用最优策略时，最后先手者和后手者各自能够取得的总石子数，并且两个整数间用一个空格隔开。


【输入输出样例1】

input                     output

8                           17  9

1 2 0 3 7 4 0 9

样例解释：两个玩家都使用最优策略时取走石子的顺序依次为9, 2, 1, 4, 7, 3，因此先手者取得9 + 1 + 7 = 17个石子，后手者取得2 + 4 + 3 = 9个石子。

【输入输出样例2】

input                     output

3                           5  0

5 0 0

输入样例 复制 

8
1 2 0 3 7 4 0 9

输出样例 复制 

17 9

分类标签