求助：状压

#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
int lm[102],s[200],num[200],s1[40000],s2[40000],num2[40000],tot,cnt1,v[200][200];
int n,m,f[102][40000];
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++) {
        char s[20];
        scanf("%s",s);
        for(int j=0; j<m; j++)
            if(s[j]=='H') lm[i]|=1<<j;
    }
    for(int i=0; i<(1<<m); i++) {
        if(i&(i<<1)||i&(i<<2)) continue;
        s[++tot]=i;
        num[tot]=__builtin_popcount(i);
    }
    for(int i=1; i<=tot; i++)
        for(int j=1; j<=tot; j++) {
            if(s[i]&s[j]) continue;
            s1[++cnt1]=i; s2[cnt1]=j;
            num2[cnt1]=num[i]+num[j];
            v[i][j]=cnt1;
        }
    if(n==1) {
        int ans=0;
        for(int i=1; i<=tot; i++)
            if(!(s[i]&lm[1])) ans=max(ans,num[i]);
        printf("%d\n",ans);
        return 0;
    }
    for(int i=1; i<=cnt1; i++) {
        if(s1[i]&lm[1]) continue;
        if(s2[i]&lm[2]) continue;
        f[2][i]=num2[i];
    }
    for(int i=3; i<=n; i++) {
        for(int j=1; j<=tot; j++) {
            if(s[j]&lm[i]) continue;
            for(int k=1; k<=cnt1; k++) {
                if(s[s1[k]]&s[j]) continue;
                if(s[s2[k]]&s[j]) continue;
                if(s[s1[k]]&lm[i-2]) continue;
                if(s[s2[k]]&lm[i-1]) continue;
                int cur=v[s2[k]][j];
                f[i][cur]=max(f[i][cur],f[i-1][k]+num[j]);
            }
        }
    }
    int ans=0;
    for(int i=1; i<=cnt1; i++) ans=max(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
}

WA2个link