The Minima Game

题目:给你 n 个数(1 <= n <= 1000000),每个数 <= 1000000000。现在两个人轮流取这些数,每次可以取若干个数,得分是这些数的最小值,直到取完为止,问在最优决策下,先手对后手的最大分差是多少。

先排序。
设dp[i]为只取前i个数的最大分差,此时新加进来一个更大的数,我们有两种策略:

  1. 取这个数但不取到这个数(最终得分小于这个数)
  2. 取并且取到这个数(最终得分就是这个数)

情况1就是dp[i],情况2就是a[i]-dp[i],因为此时该对面先取。
所以dp[i+1]=max(dp[i],a[i]-dp[i])

代码就不贴了。

Comments

comments powered by Disqus