<題目鏈接>

題目大意：

司令部的將軍們打算在N*M的網(wǎng)格地圖上部署他們的炮兵部隊。一個N*M的地圖由N行M列組成，地圖的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下圖。在每一格平原地形上最多可以布置一支炮兵部隊（山地上不能夠部署炮兵部隊）；一支炮兵部隊在地圖上的攻擊范圍如圖中黑色區(qū)域所示：?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

如果在地圖中的灰色所標(biāo)識的平原上部署一支炮兵部隊，則圖中的黑色的網(wǎng)格表示它能夠攻擊到的區(qū)域：沿橫向左右各兩格，沿縱向上下各兩格。圖上其它白色網(wǎng)格均攻擊不到。從圖上可見炮兵的攻擊范圍不受地形的影響。?
現(xiàn)在，將軍們規(guī)劃如何部署炮兵部隊，在防止誤傷的前提下（保證任何兩支炮兵部隊之間不能互相攻擊，即任何一支炮兵部隊都不在其他支炮兵部隊的攻擊范圍內(nèi)），在整個地圖區(qū)域內(nèi)最多能夠擺放多少我軍的炮兵部隊。

輸入：

第一行包含兩個由空格分割開的正整數(shù)，分別表示N和M；?
接下來的N行，每一行含有連續(xù)的M個字符('P'或者'H')，中間沒有空格。按順序表示地圖中每一行的數(shù)據(jù)。N <= 100；M <= 10。

輸出：

僅一行，包含一個整數(shù)K，表示最多能擺放的炮兵部隊的數(shù)量。

解題分析：

從形式和數(shù)據(jù)范圍來看，不難看出是一道狀壓DP的題。因為第$i$行與前兩行的狀態(tài)有關(guān)，所以我們這里用$dp[i][j][k]$來表示第$i$行為第$j$種狀態(tài)，$k$則表示上一行的狀態(tài)。

#include <cstdio> #include <algorithm> using namespace std;const int MAXR = 110, MAXC = 15, MAXM = 70; #define legal(a,b) a&bint n,m,top; int base[MAXR],state[MAXM],num[MAXM],dp[MAXR][MAXM][MAXM]; //dp[i][j][k]，表示第i行，j表示第i行的狀態(tài)，k表示第i-1行的狀態(tài) char graph[MAXR][MAXC]; inline bool ok(int x){ //在同一行的角度下，先判斷這個狀態(tài)是否可行if(x&(x<<1) || x&(x<<2))return false;return true; } inline int Count(int x){ //計算這個狀態(tài)下，該行所放士兵的數(shù)量int ans=0;while(x){ans+=x&1;x>>=1;}return ans; } inline void init(){top=0;for(int i=0;i<(1<<m);i++){if(!ok(i))continue;num[top]=Count(i); //記錄每個狀態(tài)對應(yīng)士兵的數(shù)量state[top++]=i; //預(yù)處理出初始的所有可行狀態(tài) } } int main(){scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%s",graph[i]);for(int j=0;j<m;j++)if(graph[i][j]=='H')base[i]+=1<<j;}init();for(int i=0;i<top;i++){ //初始化第一行if(legal(state[i],base[0]))continue;dp[0][i][0]=num[i];}for(int i=0;i<top;i++){ //初始化第二行 ,i表示第二行的狀態(tài)if(legal(state[i],base[1]))continue;for(int j=0;j<top;j++){ //j表示第一行的狀態(tài)if(legal(state[j],base[0]))continue;if(legal(state[i],state[j]))continue;dp[1][i][j]=max(dp[1][i][j],dp[0][j][0]+num[i]);}}for(int r=2;r<n;r++){ //枚舉第r行for(int i=0;i<top;i++){ //第r行的狀態(tài)if(legal(state[i],base[r]))continue;for(int j=0;j<top;j++){ //第r-1行的狀態(tài)if(legal(state[j],base[r-1]))continue;if(legal(state[i],state[j]))continue;for(int k=0;k<top;k++){ //第r-2行的狀態(tài)if(legal(state[k],base[r-2]))continue;if(legal(state[j],state[k]))continue;if(legal(state[i],state[k]))continue;dp[r][i][j]=max(dp[r][i][j],dp[r-1][j][k]+num[i]);}}}}int ans=0;for(int i=0;i<top;i++)for(int j=0;j<top;j++)ans=max(ans,dp[n-1][i][j]); //從最后一行的所有狀態(tài)中挑選一個最大的printf("%d\n",ans); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/00isok/p/10593748.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1185 炮兵阵地 【状压DP】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。