本文主要是介绍poj -- 1185 炮兵阵地，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题解：二进制压缩，枚举每行存在的状态，判断与前一行的状态的关系，找出最大值
dp[i][j][k] = max(dp[i][j][k] , dp[i-1][k][[l] + p[j]) 表示第i行第j个状态,i-1行的第k个状态炮兵的最大数量
#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(){//求解多少种符合的状态num = 0;for(int i = 0;i < (1<<m);i++)if(ok(i)) s[++num] = i;
}
bool find(int x,int k){//所放的炮的状态是否与山地重合if(a[k]&x) return false;return true;
}
int cal(int x){ //计算x状态下1的个数，即此状太下能放炮兵的个数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));//记录每一行有山地的状态}}memset(dp,0,sizeof(dp));memset(p,0,sizeof(p));for(int i = 1;i <= num;i++){p[i] = cal(s[i]); //p[i] 存储每种状态的的山地的个数if(find(s[i],1)) dp[1][i][1] = p[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行的状态为j，第i-1行状态为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);}
}
这篇关于poj -- 1185 炮兵阵地的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
