poj1185炮兵布陣結題報告--初步了解--狀態壓縮dp

poj1185炮兵布陣結題報告--初步了解--狀態壓縮dp

好吧，借助poj1185炮兵布陣這題，仔仔細細的了解了一下狀態壓縮動態規劃

首先，借助題目，我們來看看狀態壓縮是個蝦米東西。。Ok follow me

一，所謂狀態壓縮

根據題意，我們得在長度為M 的地圖上放置一些大炮(後面簡稱“放炮”，應該不會被和諧吧)，那麼，首先不考慮山地，我們得把所有的放置方法都找出來，並且注意，這裡只對於一行且長度為M（好吧，你可能要問考慮一行，左右互相隔2，互相不在攻擊范圍，那麼上下呢？這裡先不急，一步步來）

1，找出所有放炮的方法

假設長度為7，那麼看下圖了解放炮的方法，0表示不放，1表示放一個：

2，處理方法--引用狀態壓縮

知道了對應長度為M，一行可以放炮的狀態之後，我們就可以用這些情況，來進行解題的下一步，但是先別急，我們知道，對於長度為M，會有很多個狀態，但是我們莫非要開x*y的二維數組來保存所有狀態嗎？那麼這裡就引入了狀態壓縮：

我們知道，題目的M<= 10，並且所有的放炮的狀態我們用 01 來表示，那麼我們就可以把每一個狀態，都用一個整數了，而不是一個數組，來表示出來，如下：

那麼我們用一個數組 pao_st[ ] 來儲存所有的狀態：

pao_st[0] = 0 = (二進制) ......0000000 (這裡一個整數有32位，我們只要用到後面的即可)

pao_st[1] = 1 = (二進制) ......0000001
pao_st[2] = 2 = (二進制) ......0000010
pao_st[3] = 4 = (二進制) ......0000100 那麼這裡顯然不能有 狀態為3的情況，因為3的二進制 .....000011，那麼兩個炮相互在攻擊范圍內不符合題意

............

pao_st[cnt] = 73 = (二進制) ......1001001 那麼cnt 就表示總的狀態數量，最後一個狀態肯定是就是73，因為這種狀態時最大的啦

那麼到此，我們已經把本該cnt*7的空間開銷，變成了一個cnt的一維數組空間啦--那麼這裡就是狀態壓縮的目的-節約空間大小

那麼，對於題意M<=10，據前輩計算，最多會有 61種放置狀態

二，狀態壓縮後如何解題

OK，到上面為止，我們已經了解到了什麼是狀態壓縮，那麼我們就來在狀態壓縮後解題

1，先別急，基本方法還是要了解

那麼對於這些整數，我們都要把它當做二進制數來對待，那麼就必須要有相關的對應的操作：

‘"’，‘&’，‘^’，‘~’，‘<<’, '>>' 好吧，這些基本的東東就不一一介紹啦

2，看看怎麼用

對於上面，長度為M，我們已經得到炮的狀態pao_st[ ]，那麼考慮一個地圖的某一行，我們枚舉所有的狀態看能否用某種狀態放在這個有山地平原的地圖上呢？

那麼首先，我們也要把地圖進行二進制處理：如某一行，暫時叫做第 i 行的地圖：

PHPPPPP ------> 我們也將它對應二進制，弄一個山的狀態 shan_st[i] = (二進制) ....01000000

那麼我們只考慮第 i 行能不能放一個狀態1的時候，就可以這樣來 if(shan_[i] & pao[1])---->就說明放不了，按照上例 0100000 & 0000001 = 0000000 那麼上例就是可以放置，舉個反例 shan_[i] = 0000001，那麼shan_st[i] & pao[1] = 0000001 & 0000001 = 0000001 = 1；意思是炮放山上啦！！！不可以！！！！！

那麼這裡就可以看看前面忽略的問題：考慮上下的炮是不是能放，假設 第 i 行 放第 j 種狀態的炮pao_st[j]，第 i+1 行放第 k 種狀態的炮pao_st[k], 那麼 if(pao_st[j] & pao[k] )--->就說明放不了。。。也和上面是 一樣的意思

三，了解了基本的，那麼開始dp

首先來看看poj1185的狀態轉移方程:

dp[i][j][k]表示 當前第 i 行，狀態為 j，前一行 i-1 狀態為 k

dp[i][j][k] = max(dp[i][j][k] , dp[i-1][k][p] + sum[ j ]); 那麼這裡sum[j] 就表示 第 j 種狀態 放置炮的個數---也就是對應pao_st[ j ] 對應的二進制中 1 的個數

那麼直接上馬：代碼中的注釋更為詳細

#include 
#include 

#define MAX 105

int N,M;

char map[MAX][MAX/10];

int pao_st[61],cnt; //炮的狀態，也就是放置方法,以及狀態數量||||根據前輩計算，M<=10 狀態最多61,你也可以試試
int sum[61];//每一種狀態能放置的炮的數量
int dp[MAX][61][61];
int shan_st[MAX]; //山的狀態

int max(int a,int b) {return a>b ? a:b;}

//-----------------初始化炮的狀態，也就是初始放炮的方法-----------------begin
bool can(int x){ //判斷 x 的這種狀態---也就是二進制狀態可不可行
    if(x & (x<<1)) return false;
    if(x & (x<<2)) return false;
    return true;
}

int get_num(int x){ //x狀態的二進制狀態有多少個1，也就是此狀態的放炮數量
    int num = 0;
    while(x){
        if(x & 1) num++;
        x /= 2;
    }
    return num;
}

void init_paoSt(){ // 對於M列，初始化所有能放炮的狀態
    cnt = 0;
    for(int i = 0; i < (1< ans) ans = dp[N-1][i][j];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

在初始化山的操作中：

memset(shan_st,0,sizeof(shan_st));//--3---對於獲得的map，初始化山的狀態
for(int i = 0; i < N; i ++)
{
    for(int j = 0; j < M; j ++)
    {
        if(map[i][j] == 'H')
        {
            shan_st[i] += (1<如果山是這樣的： PHPPH，那麼從代碼中可知道，實際上我們是把它shan_st[i] 變成了這樣----> ....10010，剛好和地圖左右相反，因為這裡對應int 的32位，我們只需要後面的 10位， << 操作也是從右邊開始，對於 j = 2 的時候，1<




好吧，到現在，終於啰嗦完啦！！！
個人愚昧觀點，歡迎指正與討論！
pao_st[1] = 1 = (二進制) ......0000001
pao_st[1] = 1 = (二進制) ......0000001