炮兵陣地

Time Limit:?2000MS	?	Memory Limit:?65536K
Total Submissions:?31819	?	Accepted:?12295

Description

司令部的將軍們打算在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)最多能夠擺放多少我軍的炮兵部隊。?

Input

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

Output

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

Sample Input

5 4 PHPP PPHH PPPP PHPP PHHP

Sample Output

6

Source

Noi 01

分析：

動態(tài)規(guī)劃本來就很抽象，狀態(tài)的設(shè)定和狀態(tài)的轉(zhuǎn)移都不好把握，而狀態(tài)壓縮的動態(tài)規(guī)劃解決的就是那種狀態(tài)很多，不容易用一般的方法表示的動態(tài)規(guī)劃問題，這個就更加的難于把握了。難點在于以下幾個方面：狀態(tài)怎么壓縮？壓縮后怎么表示？怎么轉(zhuǎn)移？是否具有最優(yōu)子結(jié)構(gòu)？是否滿足后效性？涉及到一些位運算的操作，雖然比較抽象，但本質(zhì)還是動態(tài)規(guī)劃。找準(zhǔn)動態(tài)規(guī)劃幾個方面的問題，深刻理解動態(tài)規(guī)劃的原理，開動腦筋思考問題。這才是掌握動態(tài)規(guī)劃的關(guān)鍵。

狀態(tài)壓縮動態(tài)規(guī)劃最關(guān)鍵的要處理的問題就是位運算的操作，容易出錯，狀態(tài)的設(shè)計也直接決定了程序的效率，或者代碼長短。狀態(tài)轉(zhuǎn)移方程一定要仔細推敲，不可一帶而過，要思考為什么這么做，掌握一個套路，遇見這類問題能快速的識別出問題的本質(zhì)，找出狀態(tài)轉(zhuǎn)移方程和DP的邊界條件。

【題目大意】一個方格組成的矩陣，每個方格可以放大炮用0表示，不可以放大炮用1表示（原題用字母），

讓放最多的大炮，大炮與大炮間不會互相攻擊。

【解析】可以發(fā)現(xiàn)，對于每一行放大炮的狀態(tài)，只與它上面一行和上上一行的狀態(tài)有關(guān)，每一行用狀態(tài)壓縮的表示方法，0表示不放大炮，1表示放大炮，同樣的，先要滿足硬件條件，即有的地方不能放大炮，然后就是每一行中不能有兩個1的距離小于2（保證橫著不互相攻擊），這些要預(yù)先處理一下。然后就是狀態(tài)表示和轉(zhuǎn)移的問題了，因為是和前兩行的狀態(tài)有關(guān)，所以要開個三維的數(shù)組來表示狀態(tài)，當(dāng)前行的狀態(tài)可由前兩行的狀態(tài)轉(zhuǎn)移而來。即如果當(dāng)前行的狀態(tài)符合前兩行的約束條件（不和前兩行的大炮互相攻擊），則當(dāng)前行的最大值就是上一個狀態(tài)的值加上當(dāng)前狀態(tài)中1的個數(shù)（當(dāng)前行放大炮的個數(shù)）?

【狀態(tài)表示】dp[i][j][k] 表示第i行狀態(tài)為k，第i-1狀態(tài)為j時的最大炮兵個數(shù)。?

【狀態(tài)轉(zhuǎn)移方程】dp[i][k][t] =max(dp[i][k][t],dp[i-1][j][k]+num[t]); num[t]為t狀態(tài)中1的個數(shù)?

【DP邊界條件】dp[1][1][i] =num[i] 狀態(tài)i能夠滿足第一行的硬件條件（注意：這里的i指的是第i個狀態(tài)，不是一個二進制數(shù)，開一個數(shù)組保存二進制狀態(tài)）?

【代碼】

//#include<bits/stdc++.h> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int N,M; char map[110][20],num[110],top; int stk[70],cur[110]; int dp[110][70][70];//判斷該狀態(tài)是否合法，即不存在相鄰的1之間的距離小于3 inline bool ok(int x) {if(x&(x<<1)) return 0;if(x&(x<<2)) return 0;return 1; } //找到所有可能的合法狀態(tài)，最多60種 inline void jinit() {top=0;int i,total=1<<N;for(i=0;i<total;i++)if(ok(i)) stk[++top]=i; }//判斷狀態(tài)x是否與第k行匹配 inline bool fit(int x,int k) {if(cur[k]&x) return 0;return 1; }//統(tǒng)計一個整型數(shù)x的二進制中1的個數(shù)，用于初始化 inline int jcount(int x) {int cnt=0;while(x){cnt++;x&=(x-1);}return cnt; }int main() {while(scanf("%d%d",&M,&N)!=EOF){if(N==0&&M==0) break;jinit();for(int i=1;i<=M;++i)scanf("%s",map[i]+1);for(int i=1;i<=M;i++)for(int j=1;j<=N;j++){cur[i]=0;for(j=1;j<=N;j++){if(map[i][j]=='H')cur[i]+=(1<<(j-1));}}memset(dp,-1,sizeof(dp));//初始化第一行狀態(tài)for(int i=1;i<=top;i++){num[i]=jcount(stk[i]);if(fit(stk[i],1))dp[1][1][i]=num[i];}int i,t,j,k;for(i=2;i<=M;i++){for(t=1;t<=top;t++){if(!fit(stk[t],i)) continue;for(j=1;j<=top;j++){if(stk[t]&stk[j]) continue;for(k=1;k<=top;k++){if(stk[t]&stk[k]) continue;if(dp[i-1][j][k]==-1) continue;dp[i][k][t]=max(dp[i][k][t],dp[i-1][j][k]+num[t]);}}}}int ans=0;for(i=1;i<=M;++i)for(j=1;j<=top;++j)for(k=1;k<=top;++k)ans=max(ans,dp[i][j][k]);printf("%d\n",ans);}return 0; }

?

總結(jié)

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

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