【题意】：
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 【题解】：经典的状态压缩dp。
因为每行最多只有10个格子，考虑使用状态压缩。
无效的状态有很多，需要先预处理出所有合法状态，最多只有60种，存放在st[]。
设dp[i][j][k]表示当前第i行的状态为st[j]且第i-1行的状态为st[k]能够摆放部队的最大值。
转移方程：
dp[i][j][k] = max(cnt[j] + dp[i-1][k][kk])
最后的ans = max(dp[n-1][i][j]).
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 const int inf = 1 << 25;
26 int n, m;
27 char maz[110][15];
28 int row[110];
29 int dp[110][70][70];
30 int st[70], tot, cnt[70];
31
32 void init() {
33 tot = 0;
34 memset(cnt, 0, sof(cnt));
35 int nn = 1 << m;
36 for(int i = 0; i < nn; i++) {
37 bool flag = true;
38 int tmp = 0;
39 for(int j = m - 1; j >= 0; j--) {
40 if(i & (1 << j)) {
41 tmp++;
42 if((j >= 1) && (i & (1 << (j-1)))) {
43 flag = false;
44 break;
45 }
46 if((j >= 2) && (i & (1 << (j-2)))) {
47 flag = false;
48 break;
49 }
50 }
51 }
52 if(flag) {
53 st[tot] = i, cnt[tot++] = tmp;
54 }
55 }
56 }
57
58 void solve() {
59 init();
60 for(int i = 0; i < n; i++)
61 for(int j = 0; j < tot; j++)
62 for(int k = 0; k < tot; k++)
63 dp[i][j][k] = -inf;
64
65 for(int i = 0; i < tot; i++) {
66 if(!(st[i] & row[0])) dp[0][i][0] = cnt[i];
67 else dp[0][i][0] = -inf;
68 for(int j = 1; j < tot; j++) dp[0][i][j] = -inf;
69 }
70
71 for(int i = 1; i < n; i++)
72 for(int j = 0; j < tot; j++)
73 if(!(row[i] & st[j]))
74 for(int k = 0; k < tot; k++)
75 if(!(st[j] & st[k]))
76 for(int kk = 0; kk < tot; kk++)
77 if(!(st[j] & st[kk]))
78 dp[i][j][k] = max(dp[i][j][k], cnt[j] + dp[i-1][k][kk]);
79
80 int ans = 0;
81 for(int i = 0; i < tot; i++)
82 for(int j = 0; j < tot; j++)
83 ans = max(ans, dp[n-1][i][j]);
84 printf("%d\n", ans);
85 }
86
87 int main() {
88 while(~scanf("%d%d", &n, &m)) {
89 memset(row, 0, sof(row));
90 for(int i = 0; i < n; i++) {
91 scanf("%s", maz[i]);
92 for(int j = m - 1; j >= 0; j--) {
93 row[i] <<= 1;
94 if(maz[i][j] == 'H') row[i] |= 1;
95 }
96 }
97 solve();
98 }
99 return 0;
100 }
101