题目传送门
#include <bits/stdc++.h>
//https://www.acwing.com/solution/content/57859/
using namespace std;
const int N = 10;
const int M = 1 << 10; //2^10
int n, m; //n行m列，n<=100,m<=10,注意：状态压缩DP对列的长度很敏感，太大不行
int g[M]; //记录每一列的山地情况，是一个二进制标识转化后的十进制数，最大就是全都是1，也就是2^m-1
int cnt[M]; //在行是某个状态下，比如11011下，数字1的个数，也就是意大利炮的个数
vector<int> st; //记录哪些状态是合法状态
/**
第一维：已经进行到第i行
第二维：第i-1行的状态是j
第三维：第i行的状态是k
结果：所有摆放方案的意大利炮数最大值
第一维上限是行数：100
第二维的状态是2^M，就是2^10=1024
第三维的状态是2^M，就是2^10=1024
所以三维数组的空间上限就是100*1024*1024,整数一个数位占8个byte，所以空间就是
8*100*1024*1024/1024/1024=800MB，而本题要求最大空间上限64MB,所以开这么大的
数组会MLE，需要在空间上进行优化。我们联想到其实第i层的情况只与第i-1层相关，所以
可以使用滚动数组来优化。
*/
int f[2][M][M]; //滚动数组来做，防止开的太大爆掉
//检查一个状态是不是合法状态
bool check(int s) {
//遍历每一列
for (int i = 0; i < m; i++)
//连续三位，如果存在两个以上1的话，那么就是有冲突的
/*
//黄海写法
if ((s >> i & 1) + (s >> (i + 1) & 1) +
(s >> (i + 2) & 1) > 1) return false;
*/
// yxc标准写法
if ((s >> i & 1) && ((s >> (i + 1) & 1) || (s >> (i + 2) & 1)))
return false;
return true;
}
//统计某个状态中数字1的数量
int count(int s) {
int res = 0;
for (int i = 0; i < m; i++)//遍历每一列
if (s >> i & 1)res++;//如果此个位置数字是1，那么总的数量++
return res;
}
int main() {
//优化输入
ios::sync_with_stdio(false);
//输入n行m列的地图
cin >> n >> m;
for (int i = 1; i <= n; i++)//n行
for (int j = 1; j <= m; j++) {//m列
char c;
cin >> c;
//如果此位置是高地，那么需要记录高地的二进制状态标志，
//为了下面的合法性校验做准备
if (c == 'H') g[i] += 1 << (j - 1);
}
//预处理合法的状态有哪些
for (int i = 0; i < 1 << m; i++) {
if (check(i))st.push_back(i);
//预处理此状态下数字1的个数
cnt[i] = count(i);
}
for (int i = 1; i <= n; i++)
for (int j = 0; j < st.size(); j++)
for (int k = 0; k < st.size(); k++)
for (int u = 0; u < st.size(); u++) {
int a = st[j], b = st[k], c = st[u];
if ((a & b) | (b & c) | (a & c))continue;
if (g[i - 1] & a | g[i] & b) continue;
f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
}
//printf("%d\n", f[n + 2 & 1][0][0]);
int res = 0;
for (int i = 0; i < st.size(); i++)
for (int j = 0; j < st.size(); j++)
res = max(res, f[n & 1][i][j]);
cout << res << endl;
return 0;
}