二刷提高课，题解目录在这里— 提高课的题解目录

这一题状态和上两行都有关系
所以当我们只用f[i][j]来表示本行内容时，不仅与上一行有关还与上上行也有关
我们若是用f[i-1][],f[i-2][],则会导致混乱，因为我们无法清除上一行与上上行是否不合法
所以这里必须多一个状态来表示上一行
这里使用f[i][j][k]意为以枚举好第i行第i-1行状态是j第i行状态是k方案最大值
注意这里第i-1行在第二维，而第i行在第三维，上上行状态在最后一维循环中
（一般状态压缩涉及到两行状态限制都会这样表示）
只能直接进行枚举虽然次数有很多
但是有很多不合法的状态所以时间复杂度上时可以接受的
注意这里如果直接去记录会导致爆内存所以要用到滚动数组去记录

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=110,M=1<<12;
vector<int >hea;
int f[2][M][M];
int g[N];
int n,m;
int cnt[M];
bool check(int x)
{
    for(int i=0;i<m;i++)
    {
        if((x>>i&1 )&&((x>>(i+1)&1)||(x>>(i+2)&1)))return false;
    }
    return true;
}
int coun(int x)
{
    int res=0;
    while(x)
    {
        x-=x&-x;
        res++;
    }
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=0;j<m;j++)
    {
        char s;
        cin>>s;
        if(s=='H')
        g[i]+=1 << j;
    }
   for(int i=0;i<1<<m;i++)
    {
        if(check(i))
        {   
            hea.push_back(i);
            cnt[i]=coun(i);
        }    
    }
    for(int u=1;u<=n;u++)
    for(int i=0;i<hea.size();i++)
    for(int j=0;j<hea.size();j++)
    for(int k=0;k<hea.size();k++)
    {
        int a=hea[i],b=hea[j],c=hea[k];//b是本行，a是上一行
        if((a&b)||(b&c)||(c&a))continue;
        if((g[u]&b)||(g[u-1]&a))continue;
        f[u &1][i][j]=max(f[u &1][i][j],f[(u-1) &1][k][i]+cnt[b]);
        //这里有个小技巧就是偶数于1就是0
        //奇数与1就是1由于这里行数肯定是一偶一奇的
        //所以使用这种方法来实现滚动数组
    }
    int res=0;
    for(int i=0;i<hea.size();i++)
    for(int j=0;j<hea.size();j++)
    res=max(f[n&1][i][j],res);
    cout<<res;
   return 0;
}