只 A 了 #1，#2，#9……

思路是先预处理所有合法状态，然后再 DP，不会爆空间。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

const int N = 100 + 10;
const int SS = 200 + 10;
int n, m, f[N][SS][SS];
char g[N][15];
vector<int> st[N];

bool check1(int x, int S){
	for(int i=0;i<m;i++)
		if(((S >> i) & 1) && (g[x][i] == 'H'))
			return 0;
	for(int i=0;i<m-2;i++)
		if(((S >> i) & 1) && (((S >> (i + 1)) & 1) || ((S >> (i + 2)) & 1)))
			return 0;
	if(((S >> (m - 2)) & 1) && (((S >> (m - 1)) & 1)))
		return 0;
	return 1;
}

bool check2(int S1, int S2, int S3){
	for(int i=m-1;i>=0;i--)
		if(((S3 >> i) & 1) && (((S2 >> i) & 1) || ((S1 >> i) & 1)))
			return 0;
	return 1;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++)
		scanf("%s", g[i]);
	int all = (1 << m) - 1;
	
	for(int i=1;i<=n;i++){
		for(int S=0;S<=all;S++)
			if(check1(i, S))
				st[i].push_back(S);
	}
	for(int S: st[1])
		f[1][S][0] = __builtin_popcount(S);
	for(int S: st[2]){
		int d = __builtin_popcount(S);
		for(int S1: st[1])
			if(check2(0, S1, S))
				f[2][S][S1] = max(f[2][S][S1], f[1][S1][0] + d);
	}
	for(int i=3;i<=n;i++){
		for(int S: st[i]){
			int d = __builtin_popcount(S);
			for(int S1: st[i - 1]){
				for(int S2: st[i - 2]){
					if(check2(S2, S1, S))
						f[i][S][S1] = max(f[i][S][S1], f[i - 1][S1][S2] + d);
				}
			}
		}
	}
	int ans = 0;
	for(int S: st[n])
		for(int S1: st[n - 1])
			ans = max(ans, f[n][S][S1]);
	printf("%d\n", ans);
	return 0;
}