唔，想到了状压之后就不会了……实在是菜
考虑压两行，设$f_{i, j, k}$表示当前到第$i$行，上一行是$j$状态，前一行是$k$状态的最多能放的炮兵的数量。
发现第一维还可以滚掉，好像可以转移了。
但是，这样子$100 * 1024 * 1024 * 1024$时间炸了……怎么办？
考虑先不考虑题目中给出的不能放的格子的贡献，预处理出所有可行解，根据的套路，对于一个状态$i$，在这题中只要满足$i \& (i >> 1)$、$i \& (i >> 2)$、$i \& (i << 1)$、$i \& (i << 2)$全部都是$0$，那么就是一个合法状态了吧。
对于一个合法状态（记编号为$i$），只要计算出有多少个$1$就相当于可以放多少个炮兵了吧，记这个数量为$num_i$。
一行最多才$10$列，一个炮兵可以打$5$格，发现预处理之后只有$60$来个有效状态了（状态数记为$tot$），$O(ntot^3)$可以承受了。
写一下转移方程：
$f_{1, i, 0} = num_i$。
$f_{2, i, j} = max(f_{1, j, 0} + num_i)$ $i, j$不冲突且$i$和第二行的地图不冲突。
$f_{i, j, k} = max(f_{i - 1, k, t} + num_j)$ $j,k$ 、$k, t$、$j, t$不冲突且$j$和第$i$行的地图不冲突。
答案 $ans = max(f_{n, i, j})$。
注意第二行要分开处理。
时间复杂度$O(ntot^3)$，约为$O(n^4)$。
以后要记得复习！
Code:
#include#include using namespace std;const int N = 105;int n, m, a[N], tot = 0, b[N], num[N], f[N][N][N];inline void chkMax(int &x, int y) { if(y > x) x = y;}inline int bitCnt(int now) { int res = 0; for(; now > 0; now >>= 1) res += (now & 1); return res;}int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { char str[15]; scanf("%s", str + 1); for(int j = 1; j <= m; j++) if(str[j] == 'H') a[i] |= (1 << (j - 1)); } for(int i = 0; i < (1 << m); i++) if(!(i & (i << 1)) && !(i & (i << 2)) && !(i & (i >> 1)) && !(i & (i >> 2))) { ++tot; b[tot] = i, num[tot] = bitCnt(i); if(!(a[1] & b[tot])) f[1][tot][0] = num[tot]; } for(int i = 1; i <= tot; i++) for(int j = 1; j <= tot; j++) if(!(a[2] & b[j]) && !(b[i] & b[j])) chkMax(f[2][j][i], f[1][i][0] + num[j]); for(int i = 3; i <= n; i++) for(int j = 1; j <= tot; j++) { if(a[i] & b[j]) continue; for(int k = 1; k <= tot; k++) { if(b[j] & b[k]) continue; for(int t = 1; t <= tot; t++) { if((b[k] & b[t]) || (b[t] & b[j])) continue; chkMax(f[i][j][k], f[i - 1][k][t] + num[j]); } } } int ans = 0; for(int i = 1; i <= tot; i++) for(int j = 1; j <= tot; j++) chkMax(ans, f[n][i][j]); printf("%d\n", ans); return 0;}