題目鏈接：點擊查看

題目大意：中文題，題意很清晰，不多贅述

題目分析：最基礎的狀壓dp，需要考慮如何轉移，因為每一個炸彈所涉及的范圍都是上下左右兩個格子，我們可以從第一行開始向下轉移，這樣某一行的狀態就取決于前一行和前兩行，所以我們的dp數組設置為3維即可，dp[i][j][k]代表的含義是第i行，當前行狀態為j，前一行的狀態為k時的最優解，這樣我們最后在第n-1中尋找最大值即可。

接下來我們需要考慮如何優化，因為直接做的話，時間復雜度為，足足有至少1e10，那么應該會超時，那么必須優化才能做，我們首先挑選出橫向符合條件的布陣，利用了離散化的思想，即滿足條件的每相鄰兩個炮兵之間的間隔必須大于2，這樣可以減少枚舉的次數，同時在讀入地形的時候，也可以將其狀壓到一個數組中，方便利用位運算進行判斷，這樣最后的時間復雜度下降到了1e7，就可以做了

具體的話在代碼中都有注釋解釋，直接上代碼吧，還有在狀態轉移時的一系列的continue，都是剪枝用的，可以略提高運行速度

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=105;int n,m;int maze[N];//記錄每一行的地形int state[N];//記錄每一行的可行狀態 int cnt;int dp[N][N][N];//dp[i][j][k]代表第i行，當前狀態為j，前一行狀態為k時的可行方案數 int sum[N];bool check(int x)//檢查該橫向狀態是否合法 {if(x&(x<<1)||x&(x<<2))//如果有連續的炮兵隊友，則該方案不成立return false;return true; }int getsum(int x)//統計每種橫向狀態可以放置多少個炮兵 {int ans=0;while(x){if(x&1)ans++;x>>=1;}return ans; }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){memset(state,false,sizeof(state));memset(maze,0,sizeof(maze));memset(sum,0,sizeof(sum));memset(dp,-1,sizeof(dp));cnt=0;for(int i=0;i<n;i++){char str[15];scanf("%s",str);for(int j=0;j<m;j++){if(str[j]=='H')//將地形壓縮，1為山地，0為平原maze[i]|=(1<<j);}}for(int i=0;i<(1<<m);i++){if(check(i))//儲存所有合適的方案，以及該方案可以放置的炮兵數{state[cnt]=i;sum[cnt++]=getsum(i);}}for(int i=0;i<cnt;i++){if(!(state[i]&maze[0]))//初始化 dp[0][i][0]=sum[i];}for(int i=1;i<n;i++)//枚舉行數{for(int j=0;j<cnt;j++)//枚舉當前行的狀態 {if(state[j]&maze[i])//如果當前行的狀態和當前行的地形沖突 continue;for(int k=0;k<cnt;k++)//枚舉前一行的狀態 {if(state[j]&state[k])//如果前一行的狀態和當前行沖突 continue;if(state[k]&maze[i-1])//如果前一行的狀態和前一行的地形沖突 continue;for(int kk=0;kk<cnt;kk++)//枚舉前兩行的狀態{if(state[kk]&state[j])//如果前兩行的狀態和當前行沖突 continue;if(state[kk]&state[k])//如果前兩行的狀態和前一行沖突 continue;if(state[kk]&maze[i-2])//如果前兩行的狀態和前兩行的地形沖突 continue;if(dp[i-1][k][kk]==-1)//如果前兩行的狀態不存在 continue;dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][kk]+sum[j]);//狀態轉移 } }}}int mmax=0;for(int i=0;i<cnt;i++)for(int j=0;j<cnt;j++)mmax=max(mmax,dp[n-1][i][j]);//在n-1行中尋找結果cout<<mmax<<endl;}return 0; }

?

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。