对着第一篇题解打的。QAQ

emfk

#include <iostream>
using namespace std;
int f[(1<<10)][(1<<10)][3], sum[(1<<10)];
bool a[105];

inline int getsum(int S){
	int tot = 0;
	while (S) {
		tot += (S & 1);
		S >>= 1;
	}
	return tot;
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) {
			char x;
			cin >> x;
			a[i] <<= 1; a[i] += (x == 'H');
		}
	for (int i = 0; i < (1 << m); i++) {
		sum[i] = getsum(i);
		if (!(i & a[1] || i & (i << 1) || i & (i << 2))) f[0][i][1] = sum[i];
	}
	for (int i = 0; i < (1 << m); i++) { //第一行状态
		for (int j = 0; j < (1 << m); j++) { //第二行状态
			if (!(i & j || i & a[1] || j & a[2] || i & (i << 1) || i & (i << 2) || j & (j << 1) || j & (j << 2))) 
				f[i][j][2] = sum[i] + sum[j];
		}
	}
	for (int i = 3; i <= n; i++)
		for (int L = 0; L < (1 << m); L++) {
			if (L & a[i - 1] || L & (L << 1) || L & (L << 2)) continue;
			for (int S = 0; S < (1 << m); S++) {
				if (S & a[i] || L & S || S & (S << 1) || S & (S << 2)) continue;
				for (int LS = 0; LS < (1 << m); LS++) {
					if (LS & L || LS & S || LS & a[i - 2] || LS & (LS << 1) || LS & (LS << 2)) continue;
					f[L][S][i % 3] = max(f[L][S][i % 3], f[LS][L][(i - 1) % 3] + sum[S]);
				}
			}
		}
	int ans = 0, k = n % 3;
	for (int i = 0; i < (1 << m); i++)
		for (int j = 0; j < (1 << m); j++) 
			ans = max(ans, f[i][j][k]);
	cout << ans;
}