題解：二進制壓縮，枚舉每行存在的狀態(tài)，判斷與前一行的狀態(tài)的關(guān)系，找出最大值

dp[i][j][k] = max(dp[i][j][k] , dp[i-1][k][[l] + p[j]) 表示第i行第j個狀態(tài),i-1行的第k個狀態(tài)炮兵的最大數(shù)量

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int dp[105][70][70]; char map[105][20]; int a[105]; int s[70],p[70]; int n,m,num; bool ok(int x){if(x&(x<<1)) return false; //如果x的二進制里存在為類似于 11 則不滿足if(x&(x<<2)) return false; //如果x的二進制里存在為類似于 101或11，則不滿足return true; } void init(){//求解多少種符合的狀態(tài)num = 0;for(int i = 0;i < (1<<m);i++)if(ok(i)) s[++num] = i; } bool find(int x,int k){//所放的炮的狀態(tài)是否與山地重合if(a[k]&x) return false;return true; } int cal(int x){ //計算x狀態(tài)下1的個數(shù)，即此狀太下能放炮兵的個數(shù)int count = 0;while(x){count ++;x &= (x-1);}return count; } int main(){while(~scanf("%d%d",&n,&m)){init();for(int i = 1;i <= n;i++){scanf("%s",map[i]+1);a[i] = 0;for(int j = 1;j <= m;j++){if(map[i][j] == 'H') a[i] +=(1<<(j-1));//記錄每一行有山地的狀態(tài)}}memset(dp,0,sizeof(dp));memset(p,0,sizeof(p));for(int i = 1;i <= num;i++){p[i] = cal(s[i]); //p[i] 存儲每種狀態(tài)的的山地的個數(shù)if(find(s[i],1)) dp[1][i][1] = p[i]; //判定此狀態(tài)下是否與存在山地的狀態(tài)矛盾}for(int i = 2;i <= n;i++){for(int j= 1;j <= num;j++){if(!find(s[j],i)) continue;for(int k = 1;k <= num;k++){if(s[k]&s[j]) continue;for(int l = 1;l <= num;l++){if(s[l]&s[j]) continue; // if(dp[i-1][j][k] == -1) continue;dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][l] + p[j]);//用第i行的狀態(tài)為j，第i-1行狀態(tài)為k時的值}}}}int ans = 0;for(int i = 1;i <= num;i++){for(int j = 1;j <= num;j++){ans = max(ans,dp[n][i][j]);}}printf("%d\n",ans);} }

總結(jié)

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

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