P3210 [HNOI2010]取石头游戏

    • 46通过
    • 112提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 博弈论 贪心 2010 湖南 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    A 公司正在举办一个智力双人游戏比赛----取石子游戏,游戏的获胜者将会获得 A 公司提供的丰厚奖金,因此吸引了来自全国各地的许多聪明的选手前来参加比赛。

    与经典的取石子游戏相比,A公司举办的这次比赛的取石子游戏规则复杂了很多:

    l 总共有N堆石子依次排成一行,第i堆石子有 ai个石子。

    l 开始若干堆石子已被 A公司故意拿走。

    l 然后两个玩家轮流来取石子,每次每个玩家可以取走一堆中的所有石子,但有一个限制条件:一个玩家若要取走一堆石子,则与这堆石子相邻的某堆石子已被取走(之前被某个玩家取走或开始被A公司故意拿走)。注意:第 1堆石子只与第 2堆石子相邻,第N堆石子只与第N-1堆石子相邻,其余的第 i堆石子与第i-1堆和第 i+1 堆石子相邻。

    l 所有石子都被取走时,游戏结束。谁最后取得的总石子数最多,谁就获得了这场游戏的胜利。

    作为这次比赛的参赛者之一,绝顶聪明的你,想知道对于任何一场比赛,如果先手者和后手者都使用最优的策略,最后先手者和后手者分别能够取得的总石子数分别是多少。

    输入输出格式

    输入格式:

    第一行是一个正整数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: 复制
    8
    1 2 0 3 7 4 0 9
    输出样例#1: 复制
    17 9
    
    样例解释:两个玩家都使用最优策略时取走石子的顺序依次为9, 2, 1, 4, 7, 3,因此先手
    者取得9 + 1 + 7 = 17个石子,后手者取得2 + 4 + 3 = 9个石子。
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。