分数: 200 点
问题陈述
我们有 N 卡。一个数字 a_i 写在 i第一张卡。
Alice 和 Bob 将使用这些卡片玩游戏。在这个游戏中,爱丽丝和鲍勃交替拿一张牌。爱丽丝先走。
当两名玩家拿走所有牌时,游戏结束,每个玩家的分数是他/她所拿的牌上写的数字之和。当两个玩家都采取最优策略来最大化他们的分数时,找到爱丽丝的分数减去鲍勃的分数。
约束
- N 是介于 1 和 100 (含)。
- a_i \ (1 \leq i \leq N) 是介于 1 和 100 (含)。
输入
输入由标准输入按以下格式给出:
N a_1 a_2 a_3 ... a_N
输出
当两个玩家都采取最优策略来最大化他们的分数时,打印 Alice 的分数减去 Bob 的分数。
示例输入 1
2 3 1
示例输出 1
2
首先,Alice 会拿着卡片 3。然后,鲍勃将拿走卡片 1。 他们的分数之差将是 3 - 1 = 2.
示例输入 2
3 2 7 4
示例输出 2
5
首先,Alice 会拿着卡片 7。然后,鲍勃将拿走卡片 4。最后,爱丽丝将拿走卡片 2。他们的分数之差将是 7 - 4 + 2 = 5。他们的分数之差将是 3 - 1 = 2.
示例输入 3
4 20 18 2 18
示例输出 3
18