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.
很優(yōu)美的證明。。。只可惜不能提供任何strategy...-_-bbbbbbbb
最后終于悟出來這題規(guī)定棋盤3*n, n<=100,所以就100*100*100的dp就行了。。-_-bbbbbbbbbb
p.s.
wiki : Chomp Gamep.s. 確實覺得一知半解是一個很容易出錯的情況...因為如果完全不知道思維也就沒有任何限制了,曾經(jīng)看到過么...感覺會有點緊張(想要趕緊搞掉的那種感覺) & 試圖用記憶中的套路去做...但有時候可能沒有關系(例如這個game, 先手必勝的證明并不能提供任何先手如何operate的信息...,如果繼續(xù)往這個上面想就直接掛了...-_-bbbbbbb)
還有就是有可能會出現(xiàn)類似于"當時為什么不仔細推清楚"之類的念頭...這個seems容易解決...
感覺如果是完全陌生的題想法通常容易比較open, 如果感覺這個模型熟悉一般都會試圖往熟悉的模型上套...大多數(shù)情況下這樣確實可以節(jié)省時間...但是如果失去了open的思維 + 熟悉的模型無法解決就orz了...