不是很會狀態(tài)壓縮，學(xué)習(xí)一個(gè)

        定義狀態(tài)dp[row][i][j]表示當(dāng)前考慮第row行，該行狀態(tài)為i且上一行狀態(tài)為j時(shí)可安放的最大炮兵數(shù)目

        狀態(tài)轉(zhuǎn)移方程就是dp[row][i][j]=max(dp[row][i][j],dp[row-1][j][k]+num[i])，其中num[i]表示狀態(tài)i的炮兵數(shù)

        這樣看起來也不是很難嘛，不過好久沒有寫過狀態(tài)壓縮的DP了，還是要好好回憶一下這道題和之前寫過的狀壓DP的異同之處

        從狀態(tài)轉(zhuǎn)移方程可以看出，這個(gè)dp可以用滾動數(shù)組優(yōu)化

        我通過一個(gè)預(yù)處理先處理出保證同一行合法的相互狀態(tài)，然后發(fā)現(xiàn)狀態(tài)數(shù)大大減少，實(shí)際上只有88個(gè)

        至于判斷一個(gè)狀態(tài)有多少個(gè)炮兵，在我的有一篇博客就說了求出二進(jìn)制1的個(gè)數(shù)，直接拿過來用就好http://blog.csdn.net/good_night_sion_/article/details/53148718

        以下是代碼：

#include <iostream>#include <cstring>#include <vector>using namespace std;int board[105],n,m,ans,limi,dp[2][100][100],t;inline int count_bits(int x);vector<int> state;char c;void PRetreatment();int main(){    ios_base::sync_with_stdio(false);    pretreatment();    while(cin>>n>>m){        if(n==0){            cout<<0<<endl;            continue;        }        memset(board,0,sizeof board);        for(int i=1;i<=n;++i)        for(int j=0;j<m;++j){            cin>>c;            if(c=='H')                board[i]|=(1<<j);        }        limi=1<<m;        for(int i=0;state[i]<limi;++i)//處理第1行        if(!(state[i]&board[1]))            dp[t][i][0]=count_bits(state[i]);        if(n>=2){            t^=1;            for(int i=0;state[i]<limi;++i)//處理第2行            for(int j=0;state[j]<limi;++j)            if(!(state[i]&board[1])&&!(state[j]&board[2])&&!(state[i]&state[j]))                dp[t][j][i]=max(dp[t][j][i],dp[t^1][i][0]+count_bits(state[j]));        }        if(n>=3){            t^=1;            for(int row=3;row<=n;++row){                for(int i=0;state[i]<limi;++i)                if(!(state[i]&board[row]))                for(int j=0;state[j]<limi;++j)                if(!(state[j]&board[row-1])&&!(state[i]&state[j]))                for(int k=0;state[k]<limi;++k)                if(!(state[k]&board[row-2])&&!(state[k]&state[j])&&!(state[k]&state[i]))                    dp[t][i][j]=max(dp[t][i][j],dp[t^1][j][k]+count_bits(state[i]));                t^=1;            }            t^=1;        }        for(int i=0;state[i]<limi;++i)        for(int j=0;state[j]<limi;++j)            ans=max(ans,dp[t][i][j]);        cout<<ans<<endl;        ans=0;    }    return 0;}void pretreatment(){    int lim=1<<11;    for(int i=0;i<lim;++i)    if(!(i&(i>>1))&&!(i&(i>>2)))        state.push_back(i);}inline int count_bits(int x){    x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);    x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);    x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);    x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);    x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);    return x;}