500分的题。。。
由于之前看到过chomp game，(《Game Theory》的练习里有)，然后开始试图推公式之类的。。。在wiki上找到rectangle情况先手必胜的证明：
Who wins?
Chomp belongs to the category of impartial 2-player perfect information games.
It turns out that for any rectangular starting position bigger than 1 × 1 the 1st player can win. This can be shown using a strategy-stealing argument:
assume that the 2nd player has a winning strategy against any initial
1st player move. Suppose then, that the 1st player takes only the
bottom right hand square. By our assumption, the 2nd player has a
response to this which will force victory. But if such a winning
response exists, the 1st player could have played it as his first move
and thus forced victory. The 2nd player therefore cannot have a winning
strategy.
Computers can easily calculate winning moves for this game on two-dimensional boards of reasonable size.
很优美的证明。。。只可惜不能提供任何strategy...-_-bbbbbbbb
最后终于悟出来这题规定棋盘3*n, n<=100,所以就100*100*100的dp就行了。。-_-bbbbbbbbbb
p.s.
wiki : Chomp Gamep.s. 确实觉得一知半解是一个很容易出错的情况...因为如果完全不知道思维也就没有任何限制了,曾经看到过么...感觉会有点紧张(想要赶紧搞掉的那种感觉) & 试图用记忆中的套路去做...但有时候可能没有关系(例如这个game, 先手必胜的证明并不能提供任何先手如何operate的信息...,如果继续往这个上面想就直接挂了...-_-bbbbbbb)
还有就是有可能会出现类似于"当时为什么不仔细推清楚"之类的念头...这个seems容易解决...
感觉如果是完全陌生的题想法通常容易比较open, 如果感觉这个模型熟悉一般都会试图往熟悉的模型上套...大多数情况下这样确实可以节省时间...但是如果失去了open的思维 + 熟悉的模型无法解决就orz了...