这题和poj 3254很像，但是更复杂了一些
都属于棋盘里放东西，然后又各种各样的限制，然后求方案或者最大值
（1）上一道题距离要大于1，这道题是大于2。所以判断的时候变成
!(x & (x << 1) || (x & x << 2))然后关于有效状态数，可以自己输入最大的数据，例如这道题就是n=10，然后输出状态数，就可以得到等于60
（2）这道题涉及到前两行的状态。一开始觉得这道题应该是和上一道题是一样的，设第几行和状态是什么就好了
但是这样的话就不能涉及到上上行的状态。因此状态要涉及到这一行和上一行，为什么不顺便把上上行也加进来呢？因为更新的时候用到i-1是可以多往上一行的。同理，如果是往上n行，就要在状态设计中有当前这一行和往上n-2行的状态。
（3）这道题求的是最大值。那么不一定是放到最后一行的答案。所以就要把所有情况都遍历一遍求答案。
（4）还有题目输入的时候，如果是H，就要标记把这一位标记为1，如果下标从0开始的话，就可以写为1 << (m - j - 1)
但是我发现直接写1 << j也可以，因为这样只是把图左右翻过来了而已，这道题只是求最大值，不是求具体的方案，所以对答案并不会有任何影响。
#include<cstdio>
#include<vector>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 112;
const int MAXM = 70;
int dp[MAXN][MAXM][MAXM], map[MAXN];
int num[MAXM], n, m;
vector<int> state;int one(int x) { return !x ? 0 : 1 + one(x & (x - 1)); }int main()
{scanf("%d%d", &n, &m);REP(x, 0, 1 << m)if(!(x & (x << 1) || (x & x << 2))){state.push_back(x);num[state.size() - 1] = one(x);} REP(i, 0, n){char s[15];scanf("%s", s);REP(j, 0, m)if(s[j] == 'H')map[i] |= (1 << j);}REP(i, 0, state.size())if(!(state[i] & map[0]))dp[0][i][0] = num[i];REP(i, 0, state.size()){if((state[i] & map[0])) continue;REP(j, 0, state.size()){if((state[j] & map[1])) continue;if((state[j] & state[i])) continue;dp[1][j][i] = max(dp[1][j][i], dp[0][i][0] + num[j]);}}REP(r, 2, n)REP(k, 0, state.size()){if((state[k] & map[r-2])) continue;REP(j, 0, state.size()){if((state[j] & map[r-1]) || (state[j] & state[k])) continue;REP(i, 0, state.size()){if((state[i] & map[r]) || (state[j] & state[i]) || (state[i] & state[k])) continue;dp[r][i][j] = max(dp[r][i][j], dp[r-1][j][k] + num[i]);}}}int ans = 0;REP(r, 0, n)REP(i, 0, state.size())REP(j, 0, state.size())ans = max(ans, dp[r][i][j]);printf("%d\n", ans);return 0;
}