PKU1185-炮兵陣地

題目：http://poj.org/problem?id=1185
有N*M的網格圖(至多100*10)，有些格子壞了不能放大砲
大砲可以攻擊上下左右1~2格的範圍，問最多能放幾個大砲互相不攻擊


程式碼：http://codepad.org/62dWw00M

如果我高一在DP題單看到這題，我會說「DP？DP個毛阿？」

仔細想想如果只記錄f(r)代表前r橫行的砲數，也未免太過天真了
萬一前r行最多砲數的方案，剛好鎖死下一行的可能性呢？
朝著增加維度、用更詳細的狀態來消後效性
看看一橫行最多也才10格…那就…窮舉吧！

預處理得到一橫行(10格)能橫間不攻擊的方案有60種

於是很戲劇化的演化出了這樣一半暴力一半DP的「狀態壓縮DP」

這時候多記本行的狀態還不夠，不只前一行會被打、前兩行也有可能被打！

反正一行才60種，記一行不夠，那就記兩行吧。

於是得到狀態轉移
DP[r][j][i] = max(DP[r-1][k][j]+num(i) , all possible k->j->i) 沒有就給0
[前r行][當r-1行是j][當r行是i]

可以參考Corn Fields
http://nphard001.blogspot.com/2011/12/pku3254-corn-fields.html