使用状态压缩+滚动数组

注意事项：
必须用滚动数组，不然会爆空间
没有使用滚动数组时，f[i][j][k]表示当前为第i行，第i行状态为j，第i-1行状态为k。
当然，由于使用了滚动数组进行空间压缩，所以i只能取0/1，代表的是行号&1的值。

代码书写技巧：
1、可以先预处理出合法的所有状态，存起来，这样枚举的时候会好写一些。
2、位运算的优先级比较烦人，如果怕出现意外，最好全部用括号括起来，但是太难看了，而且括号太多也容易出错，所以也可以先用宏处理一下。
3、使用滚动数组时，可以用a=line&1来滚动当前的行号，很方便，而相对的，由于只有两行，那么上一行的行号当然就是a^1了。
4、获取答案的优化：在计算的时候可以多算两行，此时f[n+2][0][0]在意义上等价于问题的解，因为它表示的状态是：第n+1行和第n+2行都没有放任何部队。
5、在枚举三个状态i、j、k的时候，只判断了i与j、k之间的合法关系，而没有判断j与k之间的合法关系，这是因为如果这两者间的关系非法，那么f[line-1][j][k]代表的状态就是非法的，我们将其预处理成了负无穷，自然也不可能发生转移。
6、如果有很多重循环嵌套+if判断时，最好多用（非法状态判断+continue），可以减少嵌套层数，有时候也可以简化代码思路，理清代码结构。
7、其余用位运算简化判断的技巧，可以看yxc大佬的视频教程，就不细讲了。

C++ 代码

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=105,M=1<<11;
#define AND(a,b) ((a)&(b))
int st[N],ones[M],f[2][M][M];
vector<int> state;

int getOnes(int s){
    int cnt=0;
    for(int i=0;i<11;i++)
        cnt+=(s>>i&1);
    return cnt;
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++){
            char c;cin>>c;
            st[i]+=(c=='H')<<j;
        }
    for(int i=0;i<(1<<m);i++)
        if (!AND(i,i>>1) && !AND(i,i>>2)){
            state.push_back(i);
            ones[i]=getOnes(i);
        }
    memset(f,-0x3f,sizeof f);
    f[0][0][0]=0;
    for(int line=1;line<=n+2;line++){
        int a,b;
        a=line&1;b=a^1;
        for(auto i:state){
            if (AND(i,st[line]))    continue;
            for(auto j:state){
                if (AND(j,st[line-1]))  continue;
                for(auto k:state){
                    if (AND(i,j) || AND(i,k))
                        continue;
                    f[a][i][j]=max(f[a][i][j],f[b][j][k]+ones[i]);
                }
            }
        }
    }
    cout<<f[(n+2)&1][0][0];
    return 0;
}