500分的題。。。
由于之前看到過(guò)chomp game，(《Game Theory》的練習(xí)里有)，然后開始試圖推公式之類的。。。在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
最后終于悟出來(lái)這題規(guī)定棋盤3*n, n<=100,所以就100*100*100的dp就行了。。-_-bbbbbbbbbb
p.s.
wiki : Chomp Gamep.s. 確實(shí)覺(jué)得一知半解是一個(gè)很容易出錯(cuò)的情況...因?yàn)槿绻耆恢浪季S也就沒(méi)有任何限制了,曾經(jīng)看到過(guò)么...感覺(jué)會(huì)有點(diǎn)緊張(想要趕緊搞掉的那種感覺(jué)) & 試圖用記憶中的套路去做...但有時(shí)候可能沒(méi)有關(guān)系(例如這個(gè)game, 先手必勝的證明并不能提供任何先手如何operate的信息...,如果繼續(xù)往這個(gè)上面想就直接掛了...-_-bbbbbbb)
還有就是有可能會(huì)出現(xiàn)類似于"當(dāng)時(shí)為什么不仔細(xì)推清楚"之類的念頭...這個(gè)seems容易解決...
感覺(jué)如果是完全陌生的題想法通常容易比較open, 如果感覺(jué)這個(gè)模型熟悉一般都會(huì)試圖往熟悉的模型上套...大多數(shù)情況下這樣確實(shí)可以節(jié)省時(shí)間...但是如果失去了open的思維 + 熟悉的模型無(wú)法解決就orz了...