题目大意：在个$N*M$的地图上，有山地和平原，可以在平原上放置炮兵，炮兵可以攻击同行/同列距离$ leq 2 $的$8$个位置（不受地形影响）。给定地图，求放置炮兵方案。
题解：状压每个位置是否放炮兵，可推出dp方程，$dp_{L,S,i}$表示当前状态是$S$，上一行的状态是$L$，当前考虑到了第$i$行：
$dp_{L,S,i} = max( dp_{L,S,i} , dp_{FL,L,i-1} + count[S] )$; 这里$FL$表示上上行的状态，$count[S]$表示当前状态$S$里面包含几个$1$（有几个炮兵）。
但是这样会$Tle$，所以我们要预先处理出每一行可能的方法（同一行没有两个炮兵位置$ leq 2$）
卡点：无
C++ Code：
#include <cstdio>
using namespace std;
int n, m, dp[2][1 << 10][1 << 10], now = 1, past;
int a[111], s[1 << 9], cnt, ans;
char p[111];
int count(int x) {
int res = 0;
while (x) {
res += x & 1;
x >>= 1;
}
return res;
}
int max(int a,int b) {return a > b ? a : b;}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%s", p);
for (int j = 0; j < m; j++) a[i] |= (p[j] == 'H') << j;
}
for (int i = 0; i < (1 << m); i++)
if ((!(i & i << 1)) && (!(i & i << 2))) s[cnt++] = i;
for (int i = 0; i < cnt; i++)
for (int j = 0; j < cnt; j++)
if (((s[i] & s[j]) == 0) && ((s[i] & a[1]) == 0) && ((s[j] & a[0]) == 0)) {
dp[now][s[i]][s[j]] = count(s[i] | s[j]);
// printf("%d %d:%d
", i, j, count(i | j));
}
for (int i = 2; i < n; i++) {
now ^= past ^= now ^= past;
for (int j = 0; j < cnt; j++) if ((s[j] & a[i]) == 0) {
for (int k = 0; k < cnt; k++) if (((s[k] & a[i - 1]) == 0) && ((s[j] & s[k]) == 0)) {
for (int l = 0; l < cnt; l++) if (((s[l] & a[i - 2]) == 0) && ((s[j] & s[l]) == 0) && ((s[k] & s[l]) == 0))
dp[now][s[j]][s[k]] = max(dp[now][s[j]][s[k]], dp[past][s[k]][s[l]] + count(s[j]));
}
}
}
now ^= past ^= now ^= past;
for (int i = 0; i < cnt; i++)
for (int j = 0; j < cnt; j++) if (((s[i] & s[j]) == 0) && ((s[i] & a[n - 1]) == 0) && ((s[j] & a[n - 2]) == 0))
ans = max(ans, dp[past][s[i]][s[j]]);
printf("%d
", ans);
return 0;
}