预处理 state_r[][] 288ms
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10, M = 11, K = 1 << M;
int n, m;
char g[N][M];
vector<int> state; // state:存储所有合法的状态
int cnt[K]; // cnt[i]:i 的二进制表示中 1 的个数
vector<int> state_r[N]; // state_r[i]:存储第 i 行的所有合法状态
int f[2][K][K]; // f[i][j][k]:前 i - 2 行摆好 且第 i 行状态为 j 第 i - 1 行状态为 k 的炮台数量最大值
bool check(int x) { // 判断状态 x 是否合法
if (x & (x >> 1)) return false;
if (x & (x >> 2)) return false;
return true;
}
int lowbit(int x) { // 返回 x 的二进制表示中的最后 1 位 1
return x & -x;
}
int get(int x) { // 返回 x 的二进制表示中 1 的个数
int res = 0;
while (x) res++, x -= lowbit(x);
return res;
}
bool judge(int i, int j) { // 判断状态 j 能否放在第 i 行
for (int k = 0; k < m; k++)
if (j >> k & 1 && g[i][k + 1] == 'H') return false;
return true;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
for (int i = 0; i < 1 << m; i++) // 预处理 state
if (check(i)) state.push_back(i);
for (auto x : state) cnt[x] = get(x); // 预处理 cnt[]
for (int i = 0; i <= n + 2; i++) // 预处理 state_r[][] 注意带上 0 和 n + 1 、n + 2
for (auto x : state)
if (judge(i, x)) state_r[i].push_back(x);
for (auto x : state_r[1]) f[1 & 1][x][0] = cnt[x]; // 初始化
for (auto x : state_r[2])
for (auto y : state_r[1])
if (!(x & y)) f[2 & 1][x][y] = cnt[x] + cnt[y];
for (int i = 3; i <= n + 2; i++)
for (auto j : state_r[i]) // j 表示第 i 行的状态
for (auto k : state_r[i - 1]) // k 表示第 i - 1 行的状态
if (!(j & k))
for (auto a : state_r[i - 2]) // a 表示第 i - 2 行的状态
if (!(k & a) && !(j & a)) f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][k][a] + cnt[j]);
printf("%d", f[n + 2 & 1][0][0]);
return 0;
}
预处理 match[][] + st[][] 232ms
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10, M = 11, K = 1 << M;
int n, m;
char g[N][M];
vector<int> state; // state:存储所有合法的状态
int cnt[K]; // cnt[i]:i 的二进制表示中 1 的个数
vector<int> match[K]; // match[i] 存放所有与 i 不冲突的状态
bool st[N][K]; // st[i][j]:判断状态 j 能否放在第 i 行
int f[2][K][K]; // f[i][j][k]:前 i - 2 行摆好 且第 i 行状态为 j 第 i - 1 行状态为 k 的炮台数量最大值
bool check(int x) { // 判断状态 x 是否合法
if (x & (x >> 1)) return false;
if (x & (x >> 2)) return false;
return true;
}
int lowbit(int x) { // 返回 x 的二进制表示中的最后 1 位 1
return x & -x;
}
int get(int x) { // 返回 x 的二进制表示中 1 的个数
int res = 0;
while (x) res++, x -= lowbit(x);
return res;
}
bool judge(int i, int j) { // 判断状态 j 能否放在第 i 行
for (int k = 0; k < m; k++)
if (j >> k & 1 && g[i][k + 1] == 'H') return false;
return true;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
for (int i = 0; i < 1 << m; i++) // 预处理 state
if (check(i)) state.push_back(i);
for (auto x : state) cnt[x] = get(x); // 预处理 cnt[]
for (auto x : state) // 预处理 match[][]
for (auto y : state)
if (!(x & y)) match[x].push_back(y);
for (int i = 0; i <= n + 2; i++) // 预处理 st[][] 注意带上 0 和 n + 1 、n + 2
for (auto x : state)
if (judge(i, x)) st[i][x] = true;
// 初始化
for (auto x : state)
if (st[1][x]) f[1 & 1][x][0] = cnt[x];
for (auto x : state)
if (st[2][x])
for (auto y : match[x])
if (st[1][y]) f[2 & 1][x][y] = cnt[x] + cnt[y];
// DP
for (int i = 3; i <= n + 2; i++)
for (auto j : state) // j 表示第 i 行的状态
if (st[i][j])
for (auto k : match[j]) // k 表示第 i - 1 行的状态
if (st[i - 1][k])
for (auto a : match[k]) // a 表示第 i - 2 行的状态
if (st[i - 2][a] && !(j & a))
f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][k][a] + cnt[j]);
printf("%d", f[n + 2 & 1][0][0]);
return 0;
}