一开始数组开的暴大， MLE了，看discuss说，做多有60+的状态，所以就改成了100*100*100的数组，交上去A了，4000k+的内存，600MS+的时间， 后来看见其他人的的提交状态又快内存又少。。  后来一想，可以用滚动数组优化，改成滚动数组，就只有了200K+的内存。。。

但是，为什么么我的时间这么慢呢？时间复杂度不是O(n*nstate^3)吗＝＝



还有就是贴个代码庆祝自己花了两个晚上终于独立完成此题，虽然结果不是很理想＝＝

#include <stdio.h>
#include <string.h>

const int maxs = 1 << 11 | 1;
const int maxn = 105;

int dp[2][maxn][maxn], s[maxn], h[maxn], one[maxs];
int n, m, nstate = 0;

int Max(int a, int b) {
	return a > b ? a : b;
}

void dfs(int j, int state, int numone) {

	if (j == m) {
		s[nstate++] = state;
		one[state] = numone;

		return ;
	}
	if ((state & (1<<j-2)) || (state & (1<<j-1))) {
		dfs(j+1, state, numone);
	} else {
		dfs(j+1, state, numone);
		dfs(j+1, state | 1 << j, numone+1);
	}

	return ;
}

void CreatState() {

	dfs(0, 0, 0);

	return ;
}

int StateCompressDp() {

	int a, b, c, i, tmpa, tmpb, tmpc, max;

	for (a = 0; a < nstate; a++) {
		tmpa = s[a] & h[1];
		dp[1][a][0] = one[tmpa];
	}
	for (i = 2; i <= n; i++) {
		for (a = 0; a < nstate; a++) {
			tmpa = s[a] & h[i];
			for (b = 0; b < nstate; b++) {
				tmpb = s[b] & h[i-1];
				if (tmpa & tmpb) continue;
				max = 0;
				for (c = 0; c < nstate; c++) {
					tmpc = s[c] & h[i-2];
					if ((tmpa & tmpc) || (tmpb & tmpc)) continue;
					max = Max(max, dp[(i-1)%2][b][c]);
				}
				dp[i%2][a][b] = max + one[tmpa];
			}
		}
	}
	int ans = 0;
	for (a = 0; a < nstate; a++) {
		for (b = 0; b < nstate; b++) {
			ans = Max(ans, dp[n%2][a][b]);
		}
	}

	return ans;
}

int main () {
	
	int i, j, ans;
	char str[11];

	scanf("%d%d", &n, &m);
	getchar();
	memset(h, -1, sizeof(h));
	h[0] = 0;
	for (i = 1; i <= n; i++) {
		for (j = m-1; j >= 0; j--) {
			scanf("%c", &str[j]);
			if (str[j] == 'H') {
				h[i] = h[i] & (-1-(1<<j));
			}
		}
		getchar();
	}
	CreatState();
	ans = StateCompressDp();
	printf("%d\n", ans);

	return 0;
}