狀态壓縮經典題目（poj1184 nyoj81）

題目描述：

<dt></dt>

描述

<dd></dd>

司令部的将軍們打算在n*m的網格地圖上部署他們的炮兵部隊。一個n*m的地圖由n行m列組成，地圖的每一格可能是山地（用"h" 表示），也可能是平原（用"p"表示），如下圖。在每一格平原地形上最多可以布置一支炮兵部隊（山地上不能夠部署炮兵部隊）；一支炮兵部隊在地圖上的攻擊範圍如圖中黑色區域所示： 

如果在地圖中的灰色所辨別的平原上部署一支炮兵部隊，則圖中的黑色的網格表示它能夠攻擊到的區域：沿橫向左右各兩格，沿縱向上下各兩格。圖上其它白色網格均攻擊不到。從圖上可見炮兵的攻擊範圍不受地形的影響。 

現在，将軍們規劃如何部署炮兵部隊，在防止誤傷的前提下（保證任何兩支炮兵部隊之間不能互相攻擊，即任何一支炮兵部隊都不在其他支炮兵部隊的攻擊範圍内），在整個地圖區域内最多能夠擺放多少我軍的炮兵部隊。

分析：這個題目有個簡化版本 poj3254 ，覺得這個有難度的可以先做一下那個題目。

首先我們求的是最多能放多少個炮兵，那麼假如我把所有的情況都枚舉了，然後在得到的結果裡面找一個最大值，那麼是不是就可以了。其實這個題目的思想就是這麼簡單。

但是我們如果用一般的枚舉的方法肯定會逾時，那麼就用到了狀态壓縮。

因為這個題目中一個炮影響的是兩行，是以我們要多定義一維的狀态來表示目前行的上上一行的狀态。

狀态：dp【i】【j】【k】 第 i 行，狀态為 k ，第 i-1 行狀态為 j 的最大放的炮兵數目；

轉移方程 dp [ i ] [ k ] [ t ]  = max ( dp [ i ] [ k ] [ t ] , dp [ i - 1 ] [ j ] [ k ] + num [ t ] );

代碼：