[POJ 3317]

Stake Your Claim

博弈树搜索

题意:棋类游戏盘面大小最多8*8,两方轮流在空格落子,最后计算双方各自的最大4连通区域的大小来判胜负。空格最多10个。

题目数据范围很小,考虑到深度最多为10,一开始直接写了个O(n!)的算法,TLE。然后想明白可以用Alpha-Beta剪枝,还是TLE。最后发现空格最多10个,用位相量不过是4^10个状态,可以剔除重复状态的计算,然后就开始WA了。

持续的不解后……看了看讨论,才发现原来大家的思路都是一样的(卡了哪题都能看到ZaakDov…)。WA的原因正是Alpha-Beta剪枝导致子状态无法达到最优值,从而记录下了错误的状态值。正解是直接记忆化搜索即可。