lyht @ 2024-08-18 21:05:05
可以加上：
```cpp
n += 2, a[n - 1] = a[n] = s - 1;
```
即在最下面加上两座“长城”，这样 $n$ 就大于等于 $3$ 了。
参考代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 10) + 7;
int n, m, s, ans, a[N], c[N], f[3][N][N];
char ch;
main() {
cin >> n >> m, s = (1 << m);
for (int i = 1; i <= n; ++i) for (int j = 0; j < m; ++j)
cin >> ch, a[i] |= (ch == 'H') << j;
for (int i = 0; i < s; ++i) c[i] = __builtin_popcount(i);
for (int i = 0; i < s; ++i) if (!(i & a[1] | i & (i << 1 | i << 2)))
for (int j = 0; j < s; ++j) if (!(i & j | j & a[2] | j & (j << 1 | j << 2)))
f[0][i][j] = c[i] + c[j];
n += 2, a[n - 1] = a[n] = s - 1;
for (int i = 3; i <= n; ++i) for (int j = 0; j < s; ++j)
if (!(j & a[i - 1] | j & (j << 1 | j << 2))) for (int k = 0; k < s; ++k)
if (!(k & a[i] | k & (k << 1 | k << 2) | k & j)) for (int l = 0; l < s; ++l)
if (!(l & a[i - 2] | l & (l << 1 | l << 2) | l & j | l & k))
f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][l][j] + c[k]);
for (int i = 0; i < s; ++i) for (int j = 0; j < s; ++j) ans = max(ans, f[n & 1][i][j]);
return cout << ans, 0;
}//f[i][j][k] = 前 i 行中，第 i 行状态为 j，第 i - 1 行状态为 k 的答案
```