Posts match “ 博弈 ” tag:

http://poj.org/problem?id=3688

从i=0开始,画一颗必胜/必败态的转移树,不难分析出:
如果W只能表示成奇数个数字之和,则先手必胜。
如果W只能表示为偶数个数字之和,则后手必胜。
如果W可以表示为奇数个或偶数个数字之和,则谁胜利都有可能。

转移方程:
dp[j][1] = dp[j - a[i]][0]
dp[j][0] = dp[j - a[i]][1]

最后判断:if (dp[i][1] && !dp[i][0]) ++ans;

继续阅读

http://poj.org/problem?id=1740

规则题目没说明白:可以不移动石子到其他堆中,直接拿走就行,谁先取完谁胜利。

那么怎么讨论呢?
首先看两堆两堆相等的情况,比如n=6时,有x x y y z z这6堆,这时我们用x怎么做,对方就用另一个x同样的做,所以此类情况下先手必败。
知道这个结论后,就可以把n堆中两两相等的堆去掉,讨论去掉后互不相等的堆:

  1. 只有一堆x,先手直接全部取走,必胜;
  2. x y的形式(这里不妨假设递增,下同),先手从第二堆中取走(y-x)个石头,这样两堆相等,后手必败,先手必胜;
  3. x y z的形式,先手从z中直接拿走(z-(y-x))个石头,将剩下(y-x)个石头移到第一堆上,还是先手必胜;
  4. 去掉相等的堆后还剩下奇数个(2k+1)的情况。由于全体相邻两项之差的和必小于最后一个,所以可以用最后一堆凑出k组两两相同的堆,依旧先手必胜,后手苦逼。
  5. 去掉相等的堆后还剩下偶数个(2k)的情况。在开头加一个0个石子的堆就和4一样了。

所以统计堆数个数,若存在某一堆数的数目为奇数,则输出0。

继续阅读

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])

代码就不贴了。