0分状压求助

//dp[i][j][k]指第i行为j状态，第i-1行为k状态时的答案
#include<bits/stdc++.h>
#define ll long long
#define S (1<<10)+1
using namespace std;
ll n,m,top,ans;
ll dp[105][105][105],num[105];
ll cs[105],st[105];
bool check(ll x){//判断横向合法性
    if(x&(x<<1))return 0;
    if(x&(x<<2))return 0;
    return 1;
}
ll go(ll x){//统计该状态1的个数
    ll e=0;
    while(x){
        ++e;
        x&=(x-1);
    }
    return e;
}
int main(){
    memset(dp,-1,sizeof(dp));//初始化
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        string _s;cin>>_s;
        for(int j=0;j<_s.length();j++){
            if(_s[j]=='H')cs[i]+=(1<<(j));//处理地图
        }
        //cout<<num[i]<<endl;
    }
    for(int i=0;i<(1<<m);i++){//横向合法的就加入数组
        if(check(i))st[++top]=i;
    }
    for(int i=1;i<=top;i++){//初始化第一行
        num[i]=go(st[i]);//统计每个状态的1的个数
        //cout<<(st[i]&cs[1])<<endl;
        if(!(st[i]&cs[1])){
            dp[1][i][0]=num[i];
            ans=max(ans,dp[1][i][0]);
        }
    }
    //for(int i=1;i<=top;i++)cout<<st[i]<<endl;
    for(int i=2;i<=n;i++){//dp
        for(int j=1;j<=top;j++){
            if(st[j]&cs[i])continue;
            for(int k=1;k<=top;k++){
                if(st[j]&st[k])continue;
                for(int l=1;l<=top;l++){
                    if(st[j]&st[l])continue;
                    if(dp[i-1][k][l]==-1)continue;
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+num[j]);
                }
                if(i==n)ans=max(ans,dp[i][j][k]);
            }
        }
    }
    printf("%lld",ans);
    return 0;
}