P3507 [POI2010]GRA-The Minima Game

    • 384通过
    • 692提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 模拟 贪心 POI 2010 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示


    Alice and Bob learned the minima game, which they like very much, recently.

    The rules of the game are as follows.

    A certain number of cards lies on a table, each inscribed with a positive integer.

    The players make alternate moves, Alice making the first one.

    A move consists in picking an arbitrary positive number of cards from the table.

    For such move the player receives a number of points equal to the minimum of the numbers inscribed on the cards he collected.

    The game ends when the last card is removed from the table.

    The goal of each player is maximizing the difference between their and their opponent's score.

    Alice and Bob have duly noted that there is an optimal strategy in the game.

    Thus they are asking you to write a program that, for a given set of cards, determines the outcome of the game when both players play optimally.




    In the first line of the standard input there is one integer () given, denoting the number of cards.

    The second line holds positive integers (), separated by single spaces, that are inscribed on the cards.


    Your program should print out a single line with a single integer to the standard output - the number of points by which Alice wins over Bob, assuming they both play optimally; if it is Bob who has more points, the result should be negative.


    输入样例#1: 复制
    1 3 1
    输出样例#1: 复制