本文主要是介绍poj 1185 炮兵阵地（动态规划：状压DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
用二进制数表示一行的状态
预处理记录满足条件的状态对应十进制数
因为当前行仅与上两行有关，所以状态转移方程为：
dp[i][k][t] = max(dp[i][k][t], dp[i-1][j][k]+num[t])
num[t]表示状态t对应的炮台数
dp[i][k][t]表示第i行状态为t,第i-1行状态为k时对应的最大值
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100
using namespace std;int m, n, top;
int dp[120][MAXN][MAXN];
int state[MAXN], num[MAXN];
int cur[120];
char str[MAXN];bool ok(int x) {if(x & (x<<1)) return 0;if(x & (x<<2)) return 0;return 1;
}int count(int x) {int cnt = 0;while(x) {++cnt;x &= x-1;}return cnt;
}void init() {top = 0;int total = 1<<n;for(int i=0; i<total; ++i) {if(ok(i)) {state[++top] = i;}}
}bool fit(int x, int k) {if(x & cur[k]) return 0;return 1;
}int main(void) {while(scanf("%d%d", &m, &n) != EOF && (m||n)) {init();for(int i=1; i<=m; ++i) {cur[i] = 0;scanf("%s", str);for(int j=0; j<n; ++j) {if(str[j] == 'H') {cur[i] += 1<<j;}}}memset(dp, -1, sizeof(dp));for(int i=0; i<=top; ++i) {num[i] = count(state[i]);//printf("state[%d] = %d\t %d\n", i, state[i], num[i]);if(fit(state[i], 1))dp[1][1][i] = num[i];}for(int i=2; i<=m; ++i) {for(int t=1; t<=top; ++t) {if(!fit(state[t], i))continue;for(int j=1; j<=top; ++j) {if(state[t] & state[j])continue;for(int k=1; k<=top; ++k) {if(state[k] & state[t])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(int i=1; i<=m; ++i) {for(int j=1; j<=top; ++j)for(int k=1; k<=top; ++k)ans = max(ans, dp[i][j][k]);}printf("%d\n", ans);}return 0;
}这篇关于poj 1185 炮兵阵地（动态规划：状压DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
