poj 1185 炮兵布陣最詳細題解（狀壓DP經典）

2019-11-11 02:13:44

字體：大中小

來源：轉載

供稿：網友

炮兵陣地

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 26796		Accepted: 10344

Description

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

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

Input

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

Output

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

Sample Input

5 4phpPPPHHPPPPPHPPPHHPSample Output
6先發兩個網上比較好的題解，再說下自己的理解
題解1:
由于是求的最多能放置的炮兵個數，就是求某一個狀態下，它對應的炮兵個數最多，所以就想到dp方程肯定是那種dp[i+1]=max{dp[i-1]..}的形式，又考慮到每一行
的狀態只和前兩行有關系，所以考慮用dp來做，下面考慮如何用二進制位來表示一個狀態及轉移方程。
對于原始的矩陣，我們用1來表示可以放置炮兵，即對應圖中的P，這樣每一行都有一個可以放置炮兵的狀態，存到rstate[N]中，用來check該行的狀態是否合法。
由于當前行和前兩行有關系，所以得用3維矩陣來保存一個狀態下最多的炮兵個數，用dp[i][curst][PRest]表示當前第i行狀態對curst，前一行狀態為prest的最大炮兵數。
轉移方程為dp[i][curst][prest]=max{dp[i-1][prest][preprest]}，這樣求到最后一行之后，答案就是最后一行所有狀態中最大的那個。程序初始化的時候需要對第一行
進行預處理，設置dp[0][st][0]=st合法&st中1的個數。這樣進行下面的計算的時候，由于0狀態肯定是和所有狀態兼容的，所以就不會影響計算結果。
題解2：
思考方法：首先，一個炮的攻擊有兩行，所以對于第i行來講，i-1行和i-2行對它有影響，i-3行及以上的都沒有影響了，所以我們要得到第i行的信息，只需要知道i-1和i-2的信息（最近有個體會，DP要找到什么因素影響了當前你要求的東西，有影響的我們就處理，沒影響的我們不用管）。接著我們就思考怎么表示狀態。山用1表示，空地用0表示，空地放了兵也用1表示，那么對于一行，就是一個01的串，這是個二進制數，我們可以想到狀態壓縮壓縮回來一個十進制數。
比如原地圖01101011，那么0處可以放兵，所有那么多個0，可以變為1（但也要考慮炮與炮之間不能攻擊），要枚舉全部情況，我們很自然想到了dfs來枚舉，很多解題報告是這樣做的，這樣確實也能解決，但不是最好的方法。最好的方法是位運算。
要想到位運算，要跳出思維的限制，在一行中，原有的1是固定不能變，炮不能放在山上。0是可以變為1的，但是要保證炮與炮之間不能攻擊。要滿足這兩個要求，我們可以拆開來做。先滿足了炮與炮不能互相攻擊，然后在這些擺放中再選出跑不在山上的。
只考慮炮的話，枚舉量2^10-1，但實際上滿足的不足60個，網上有人問過60是怎么計算的，實際上準確的做法我也不確定，但是能大概推出來。一列最多10位，最多其實只能放4個炮，然后接著看3個炮，2個炮，1個炮，0個炮的情況，就可以大致算出。
枚舉方法是   for(i=0; i<(i<<col); i++)  if( !(i&(i<<1)) & !(i&(i<<2)) )  i是合法狀態   這個是要點，要理解    
int state[MAXM];  保存狀態（十進制數），是僅僅滿足了炮與炮不互相攻擊，但是沒有滿足炮不在山上
對于一開始的地圖，還沒放炮，它本身已經表示了一個狀態，所以也先壓成一個狀態，保存在一個數組中
再者，我們得到了一個狀態state[i]，我們怎么知道這個狀態下放了多少炮?。科鋵嵕褪桥袛鄐tate[i]這個十進制數變為二進制數后有多少個1，這個要怎么統計呢？位運算！
并且把對應的士兵人數保存在  int soldier[MAXM]; //對應著，在state[i]狀態下能放多少個士兵
int base[MAXR];  //第i行的原地圖壓縮成的一個狀態
那么怎么判斷炮不在山上呢？  只要state[i] & base[r] = 0 ,就表示state[i]這個狀態，可以放在r這行上，而且炮不會在山上，炮之間也不會攻擊，這是個要點，理解
 
然后前面說了，i行，i-1行，i-2行的炮會互相影響，他們可能會互相攻擊到對方，所以我們假設現在i行，i-1行，i-2行的炮的擺放情況分別是state[i],state[j],state[k]
只有當他們都不兩兩攻擊的時候，這3個狀態才能放在一起，否則這3個狀態不能放在一起。那么怎么判斷他們不會兩兩攻擊呢，方法一樣的
state[i] & state[j] = 0   state[i] & state[k] = 0     state[j] & state[k] = 0   ，三個要同時滿足，要點，理解
你會發現多次需要用到 一種判斷  a&b  是為0還是不為0，所以我們代碼中將其寫成宏定義方便查看，實際上寫成宏后時間慢了一點
#define legal(a,b) (a&b) //判斷兩個狀態共存時是否合法，合法為0，不合法為非0 
 
最后看狀態轉移方程，設dp[r][i]表示第r行，狀態為state[i]是的最大值，
dp[r][i]=max { dp[r-1][j]+dp[r-2][k] } + soldier[i]
也就是第r-1行的狀態為state[j]，第r-2行的狀態為state[k]的和，并加上當前行放了soldier[i]個士兵 ， 但要滿足state[i],state[j],state[k]不能互相攻擊
接著我們可以可以寫成三維的形式 dp[r][i][j]= max{ dp[r-1][j][k]} + soldier[i]  ,  dp[r][i][j]表示第r行狀態為state[i]，第r-1行為state[j]的最大值
 
做題感悟：
之前做的兩個狀壓DP都是選擇的，即用了就不能再用了，所以就只是跳過標記的就行，而且一開始都是0，并沒有像這題有地圖限制，所以可以直接dfs，因為他不像這題有地形限制，所以像這類有地形限制的，比如標記一個點四周兩個點都被標記，這樣的，一般要初始化，先把所有可行的狀態都找出來，這個題每一行，每個炮臺左右兩個格以內不能再有炮臺，也就是每個1左右兩邊兩個格子必須都是0，用位運算表示就是!(i&(i<<1)) && !(i&(i<<2))，把i的整體狀態都左移1個跟兩個，這樣就可以看每個1左右兩個空格有沒有1了。。如果沒有1，這說明就是一個可行的狀態，就把他記錄下來，這樣每個炮臺這一行的問題就解決了，直接枚舉所有可行狀態就行，那么這個炮臺又只跟前面兩行有關了，從第一行枚舉過去，這個炮臺下面的兩個其實不用管，枚舉過去就好了(類似反轉問題），這個記錄狀態要學習一下。。。
由于當前行和前兩行有關系，所以得用3維矩陣來保存一個狀態下最多的炮兵個數，用dp[i][curst][prest]表示當前第i行狀態對curst，前一行狀態為prest的最大炮兵數。
轉移方程為dp[i][curst][prest]=max{dp[i-1][prest][preprest]}，這樣求到最后一行之后，答案就是最后一行所有狀態中最大的那個。程序初始化的時候需要對第一行
前面的狀態注意要跟分別跟前兩行的地圖比較下，這個題就差不多解出來了。
心得就是，像這種有特殊限制的，比如四周不能有等等，就提前初始化，把所有的情況都記錄在一個數組，然后枚舉情況就好了，其余的簡單的，比如每一行只有一個，每一列只有一個，這樣的完全可以直接dfs 比如這題：http://blog.csdn.net/QQ_34374664/article/details/54586529，還有狀壓dp其實“每一行的可行狀態都是一樣的”，枚舉行的之后其實都是枚舉相同的狀態。。
我的代碼：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define me(a) memset(a, 0, sizeof(a))using namespace std;int dp[115][70][70], maze[105], status[70], num[70], m, n, len;char str[111];int main(){    while(~scanf("%d%d", &n, &m))    {        me(dp);        me(num);        me(maze);        me(status);        for(int i = 1; i <= n; i++)        {            scanf("%s", str);            for(int j = 0; j < m; j++)            {                if(str[j] == 'H')                {                    maze[i] += (1<<j);                }            }        }        len = 1;        for(int i = 0;i < (1<<m); i++)        {            if(!(i&(i<<1)) && !(i&(i<<2)))            {                int k = i, sum = 0;                while(k)                {                    if(k&1)                        sum++;                    k >>= 1;                }                num[len] = sum;                status[len++] = i;            }        }        for(int i = 1; i < len; i++)        {            if(!(maze[1]&status[i]))            {                dp[1][i][1] = num[i];            }        }        for(int i = 2; i <= n; i++)        {            for(int j = 1; j < len; j++)            {                if(status[j]&maze[i]) continue;                for(int k = 1; k < len; k++)                {                    if(status[j] & status[k]) continue;                    if(status[k] & maze[i-1]) continue;                    for(int t = 1; t < len; t++)                    {                        if(status[t]&status[j]) continue;                        if(status[t]&status[k]) continue;                        if(status[t]&maze[i-2]) continue;                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][t]+num[j]);                    }                }            }        }        int ans = 0;        for(int i = 1;i < len; i++)            for(int j = 1;j < len; j++)                 ans = max(ans, dp[n][i][j]);        printf("%d/n", ans);    }    return 0;}一個比較詳細的代碼：
#include <cstdio>#include <iostream>#include <cstring>#define MAXR 110 //行數#define MAXC 15  //列數#define MAXM 70  //狀態數#define max(a,b) a>b?a:b //返回較大值#define CL(a) memset(a,0,sizeof(a)) //初始化清空數組#define legal(a,b) a&b //判斷兩個狀態共存時是否合法，合法為0，不合法為非0int row,col;  //行列int nums;  //僅是兩個炮兵不互相攻擊的條件下，符合條件的狀態個數int base[MAXR];  //第i行的原地圖壓縮成的一個狀態int state[MAXM]; //僅是兩個炮兵不互相攻擊的條件下，符合條件的狀態（一個十進制數）int soldier[MAXM]; //對應著，在state[i]狀態下能放多少個士兵int dp[MAXR][MAXM][MAXM];//dp[i][j][k] 表示第i行狀態為state[j]，第i-1行狀態為state[k]時的最優解char g[MAXR][MAXC];using namespace std;int main(){    CL(base); CL(state); CL(soldier); CL(dp);    nums=0;    scanf("%d%d",&row,&col);    for(int i=0; i<row; i++)  //先計算原始地圖的狀態數    {        scanf("%s",g[i]);        for(int j=0; j<col; j++)        if(g[i][j]=='H') base[i]+=1<<j; //像0110000，這里計算為6    }    for(int i=0; i<(1<<col); i++)  //僅是兩個炮兵不互相攻擊的條件下計算所有狀態    {        if( legal(i,i<<1) || legal(i,i<<2)) continue; //i這個狀態出現了士兵兩兩攻擊        int k=i;        while(k) //這個循環計算狀態i的二進制形式里面有多少個1，也就是放了多少個士兵        {            soldier[nums]+=k&1; //等價于k%2，相當于判斷k的二進制形式里面有多少個1            k=k>>1;        }        state[nums++]=i; //保存這個合法的狀態    }    /***************************************/    //for(int i=0; i<nums; i++) printf("%d %d/n",state[i],soldier[i]);    /***************************************/    for(int i=0; i<nums; i++) //先初始化dp[0][i][0]，即初始化第1行的情況    {        if(legal(state[i],base[0])) continue;        //在state[i]的基礎上，還要滿足士兵不能放在山上，這個判斷就是處理這個問題的        dp[0][i][0]=soldier[i];    }//    for(int i=0; i<nums; i++) //接著初始化dp[1][i][j]，即第2行的情況//    {//        if(legal(state[i],base[1])) continue;//        for(int j=0; j<nums; j++) //枚舉第1行的狀態//        {//            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]+soldier[i]);//            //狀態轉移方程//        }//    }    for(int r=1; r<row; r++) //第3行開始DP直到最后        for(int i=0; i<nums; i++) //枚舉第r行的狀態        {            if(legal(state[i],base[r])) continue;            for(int j=0; j<nums; j++) //枚舉第r-1行的狀態            {                if(legal(state[j],base[r-1])) continue;                if(legal(state[i],state[j])) continue;                //第r行的士兵和第r-1行的士兵相互攻擊                for(int k=0; k<nums; k++) //枚舉第r-2行的狀態                {                    if(legal(state[k],base[r-2])) continue;                    if(legal(state[j],state[k])) continue;                    //第r-1行的士兵和第r-2行的士兵相互攻擊                    if(legal(state[i],state[k])) continue;                    //第r行的士兵和第r-1                    dp[r][i][j]=max(dp[r][i][j] , dp[r-1][j][k]+soldier[i]);                }            }        }    int ans=0;    for(int i=0; i<nums; i++)        for(int j=0; j<nums; j++) //枚舉dp[row-1][i][j]           ans=max(ans,dp[row-1][i][j]);    printf("%d/n",ans);    return 0;}