题意：给出一张n * m的地图，其中 有的地方能放大炮，有的地方不能，大炮与上下左右两个单位范围内会相互攻击，问最多能放几个大炮
能放大炮为1不能放大炮为0，把每一行看做一个状态，要除去同一行与前面两个相邻的情况，然后在除去与上面两行相邻的情况，因为涉及前面两行所以多设一维状态
dp[i][j][k]表示 第 i 行 状态为k时，第i - 1行状态为j，
那么dp[i][j][k] = max ( dp[i][j][k], dp[i - 1][t][j] + num[k])； num[k]表示第i行可以放多少门大炮，也就是k状态下1的个数
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int state[200], num[200]; int cur[110]; char g[110][20]; int dp[110][200][200]; int n, m, top, total; inline bool is_ok(int x) { if (x & (x << 1)) return 0; if (x & (x << 2)) return 0; return 1; } int jcount(int x) { int cnt = 0; for (int i = 0; i < 12; i++) if (x & (1 << i)) cnt++; return cnt; } int fit(int x, int i) { if (x & cur[i]) return 0; return 1; } void init() { top = 0; total = 1 << m; for (int i = 0; i < total; i++) { if (is_ok(i)) state[++top] = i; } } int main() { while (scanf("%d%d", &n, &m) != EOF) { init(); for (int i = 1; i <= n; i++) { cur[i] = 0; scanf("%s", g[i] + 1); for(int j = 1; j <= m; j++) if (g[i][j] == 'H') cur[i] += (1 << (j - 1) ); //同上一题一样将不能放炮的设为1，这样 & 的话只要非0就不行，因为一定含有不能放炮的而放炮了，0是允许放炮，但是放不放都行，也就是0,1随便，都是可以的 } memset(dp, -1, sizeof(dp)); int ans = -1; for (int i = 1; i <= top; i++) { num[i] = jcount(state[i]); // 求出每一种状态下能放得炮数 if (!fit(state[i], 1)) continue; dp[1][1][i] = num[i]; //第一行状态为state[i],第0行状态为state[1] = 0 ans = max(ans, num[i]); } for (int i = 2; i <= n; i++) { for (int t = 1; t <= top; t++) { if (!fit(state[t], i)) continue; for (int j = 1; j <= top; j++) // 第 i - 1行的情况 { if (state[t] & state[j]) continue; for (int k = 1; k <= top; k++) //第i - 2行的情况 { if (state[t] & state[k]) continue; if (dp[i - 1][k][j] != -1) // 不符合要求的，dp[1][1][其他] ,而第0行其他状态都没有 { dp[i][j][t] = max(dp[i][j][t], dp[i - 1][k][j] + num[t]); ans = max(ans, dp[i][j][t]); } } } } } printf("%d ", ans); } return 0; }