首页 > 代码库 > Beans Game(博弈 | | DP)zoj 3057
Beans Game(博弈 | | DP)zoj 3057
There are three piles of beans. TT and DD pick any number of beans from any pile or the same number from any two piles by turns. Who get the last bean will win. TT and DD are very clever.
Input
Each test case contains of a single line containing 3 integers a b c, indicating the numbers of beans of these piles. It is assumed that 0 <= a,b,c <= 300 and a + b + c > 0.
Output
For each test case, output 1 if TT will win, ouput 0 if DD will win.
Sample Input
1 0 01 1 12 3 6
Sample Output
100
博弈题；相对于取石子游戏那题多了一堆；（但，有一点不一样，就是范围！那么就简单多了）
题目大意：有三堆豆子a,b,c(a+b+c<=300)。TT和DD轮流从其中一堆拿走任意个豆子或从其中的两种拿走同样多的豆子，最后一个拿完的获胜。
算法分析：
典型的威佐夫博弈问题是两堆，而此题为三堆。
原本以为这题是要找规律，但是找了一个小时没找到。百度解题报告，发现原来只要逆向推即可。采用递推比较快。
p[i][j][k] = 0表示状态为i,j,k时是必败态，p[i][j][k] = 1为必胜态。
从必败态往上推，能从必败态推出来的就是必胜态，赋值为1，如果是必胜点就不用往上推了。
p[i][j][k]初始化为必败点，如果该点不能从必败点转移过来，该点就是必败点。
由于必败点比较少所以可以节省时间。
Beans Game(博弈 | | DP)zoj 3057
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。