P2704炮兵阵地

不知道为什么样例都没过（输出8）QWQ

#include <bits/stdc++.h>
#define PII pair <int, int>
#define int long long
#define DB double

namespace FastIO
{
	inline void read(int MOD, int &ret){
		ret = 0;
		char ch = getchar();int ngtv = 1;
		if(MOD == 0) {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = (ret << 3) + (ret << 1) + (ch ^ 48);ch = getchar();}}
		else {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = (((ret << 3) + (ret << 1)) % MOD + (ch ^ 48) % MOD) % MOD;ch = getchar();} }
		ret *= ngtv;}
	inline void cread(char &ch){ch = getchar();while(ch == ' ' || ch == '\n' || ch == '\r' || ch == 0) ch = getchar();}
}
using namespace FastIO;
using namespace std;

const int N = 110, M = 1200;
int n, m, a[N];
int cnt, ans, sit[M], gs[M], dp[N][M][M];
string str;

void dfs(int x, int y, int z)
{
	if(x >= n)
	{
		sit[ ++ cnt] = y;
		gs[cnt] = z;
		return ;
	}
	dfs(x + 1, y, z);
	dfs(x + 3, y + (1 << x), z + 1);
}

signed main()
{
	read(0, n), read(0, m);
	dfs(0, 0, 0);
	a[0] = (1 << m) - 1;
	for(int i = 1; i <= n; i ++ )
	{
		cin >> str;
		for(int j = 0; j < m; j ++ )
			a[i] = a[i] + ((str[j] == 'H') << j);
	}

	for(int i = 1; i <= cnt; i ++ )
	{
		if(!(sit[i] & a[1]))
			dp[1][i][1] = gs[i];
	}
	for(int i = 1; i <= cnt; i ++ )
	{
		for(int j = 1; j <= cnt; j ++ )
		{
			if(i == j) continue;
			if(sit[i] & sit[j]) continue;
			dp[2][i][j] = gs[i] + gs[j];
		}
	}
	
	for(int i = 3; i <= n; i ++ )
	{
		for(int j = 1; j <= cnt; j ++ )
		{
			if(sit[j] & a[i]) continue;
			for(int k = 1; k <= cnt; k ++ )
			{
				if(j == k) continue;
				if(sit[j] & sit[k]) continue;
				if(sit[k] & a[i - 1]) continue;
				
				for(int l = 1; l <= cnt; l ++ )
				{
					if(j == l) continue;
					if(k == l) continue;
					if(sit[j] & sit[l]) continue;
					if(sit[k] & sit[l]) continue;
					if(sit[l] & a[i - 2]) continue;
					dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + gs[j]);
				}
			}
		}
	}
	
	for(int i = 1; i <= cnt; i ++ )
	{
		for(int j = 1; j <= cnt; j ++ )
		{
			ans = max(ans, dp[n][i][j]);
			printf("%d %d %d\n", i, j, dp[n][i][j]);
		}
	}
	printf("%d\n", ans);
		
    return 0;
}