题意：如下图所示，给出n*m的网格，其中P表示能放炮兵，H表示不能放，每只炮兵的射程如图涂黑部分。在防止误伤的前提下(任何一个炮兵不在其他炮兵的射程内)，问最多能拜访多少炮兵。(n <= 100, m <= 10)
解法：首先，预处理出在某行全为P的情况下，该行能合法拜访炮兵方法对应的状态，发现只有60种。
设d[i][j][k]表示第i行状态为j，第i-1行状态为k的情况下，最多能拜访多少炮兵。
d[i][j][k] = max(d[i-1][k][l] + num(j))，其中l表示(l, k)能转移成(k, j)的状态，而num(j)表示j状态下该行有多少个炮兵。
tag:状压dp
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-11-19 09:12 4 * File Name: DP-POJ-1185.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <vector> 10 11 using namespace std; 12 13 #define CLR(x) memset(x, 0, sizeof(x)) 14 #define PB push_back 15 16 int n, m, sz; 17 bool a[200][20]; 18 int d[105][70][70]; 19 vector<int> sta; 20 vector<int> pat[70][70]; 21 22 int xxx; 23 24 bool gao1(int opt) 25 { 26 for (int i = 0; i < m; ++ i) 27 if (opt & (1<<i)){ 28 if (i && (opt & (1<<(i-1)))) return 0; 29 if (i > 2 && (opt & (1<<(i-2)))) return 0; 30 if (i < m-1 && (opt & (1<<(i+1)))) return 0; 31 if (i < m-2 && (opt & (1<<(i+2)))) return 0; 32 } 33 return 1; 34 } 35 36 bool gao2(int opt, int num) 37 { 38 for (int i = 0; i < m; ++ i) 39 if ((opt & (1<<i)) && !a[num][i]) 40 return 0; 41 return 1; 42 } 43 44 bool gao3(int t1, int t2, int t3) 45 { 46 int tmp[3]; 47 tmp[0] = t1; tmp[1] = t2; tmp[2] = t3; 48 49 for (int i = 0; i < m; ++ i){ 50 int tim = 0; 51 for (int j = 0; j < 3; ++ j) 52 if (tmp[j] & (1<<i)) ++ tim; 53 if (tim > 1) return 0; 54 } 55 return 1; 56 } 57 58 int get_num(int x) 59 { 60 int ret = 0; 61 for (int i = 0; i < m; ++ i) 62 if (x & (1<<i)) ++ ret; 63 return ret; 64 } 65 66 void init() 67 { 68 char x; 69 for (int i = 0; i < n; ++ i) 70 for (int j = 0; j < m; ++ j){ 71 x = 'a'; 72 while (x != 'P' && x != 'H') scanf ("%c", &x); 73 if (x == 'P') a[i][(m-1-j)] = 1; 74 else a[i][(m-1-j)] = 0; 75 } 76 77 sta.clear(); 78 for (int i = 0; i < (1<<m); ++ i) 79 if (gao1(i)) sta.PB(i); 80 sz = sta.size(); 81 82 for (int i = 0; i < sz; ++ i) 83 for (int j = 0; j < sz; ++ j) 84 pat[i][j].clear(); 85 86 for (int i = 0; i < sz; ++ i) 87 for (int j = 0; j < sz; ++ j) 88 for (int k = 0; k < sz; ++ k) 89 if(gao3(sta[i], sta[j], sta[k])) 90 pat[i][j].PB(k); 91 } 92 93 int DP() 94 { 95 CLR (d); 96 for (int i = 0; i < sz; ++ i) 97 if (gao2(sta[i], 0)) d[0][i][0] = get_num(sta[i]); 98 99 for (int i = 1; i < n; ++ i) 100 for (int j = 0; j < sz; ++ j) 101 for (int k = 0; k < sz; ++ k) 102 if (gao2(sta[j], i) && gao2(sta[k], i-1)){ 103 d[i][j][k] = 0; 104 for (int l = 0; l < (int)pat[j][k].size(); ++ l) 105 d[i][j][k] = max(d[i][j][k], d[i-1][k][pat[j][k][l]] + get_num(sta[j])); 106 } 107 108 int ret = 0; 109 for (int i = 0; i < sz; ++ i) if (gao2(sta[i], n-1)) 110 for (int j = 0; j < sz; ++ j) if (gao2(sta[j], n-2)) 111 ret = max(ret, d[n-1][i][j]); 112 return ret; 113 } 114 115 int main() 116 { 117 while (scanf ("%d%d", &n, &m) != EOF){ 118 init(); 119 printf ("%d ", DP()); 120 } 121 return 0; 122 }