90分 WA #9求助

P2704 [NOI2001] 炮兵阵地

#include <iostream>
#include <cstring>
using namespace std;

int n,m,cnt[1<<12],num[1<<12],s[110][1<<12],f[110][110][110];
char c[110][12];

void init(){
    for(int i=0;i<(1<<m);i++){
        if(i&(i<<1)||i&(i<<2)||i&(i>>1)||i&(i>>2))continue;
        for(int j=1;j<=n;j++){
            int sum=0,flag=0;
            for(int k=0;k<m;k++){
                if(i&(1<<k)){
                    if(c[j][m-k]=='H'){
                        flag=1;
                        break;
                    }
                    sum++;
                }
            }
            if(flag)continue;
            s[j][++cnt[j]]=i;
            num[i]=sum;
        }
    }
    return ;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>c[i][j];
    init();
/*  memset(f,-127,sizeof(f));
    for(int i=0;i<=(1<<11);i++){
        for(int j=0;j<=(j<<11);j++){
            f[0][i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cnt[i];j++){
            cout<<num[s[i][j]]<<" ";
        }
        cout<<endl;
    }*/
    for(int i=1;i<=cnt[1];i++)  //处理第一排
            f[1][i][0]=num[s[1][i]];
    for(int i=1;i<=cnt[1];i++){ //第二排
        for(int j=1;j<=cnt[2];j++){
            if(!(s[1][i]&s[2][j])){ //判断是否冲突
                f[2][i][j]=num[s[1][i]]+num[s[2][j]];
            } 
        }
    }
    for(int i=3;i<=n;i++){//枚举行 
        for(int j=1;j<=cnt[i];j++){//枚举第i行状态 
            for(int k=1;k<=cnt[i-1];k++){//枚举第i-1行状态 
                if(!(s[i][j]&s[i-1][k]))
                for(int l=1;l<=cnt[i-2];l++){//枚举第i-2行状态
                    if(!(s[i][j]&s[i-2][l])&&!(s[i-1][k]&s[i-2][l]))
                    f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+num[s[i][j]]);
                    //cout<<"i: "<<i<<"  j: "<<j<<"  k: "<<k<<"  l: "<<l<<" -> "<<f[i][j][k]<<endl;
                }
            }
        }
    }
/*  for(int i=1;i<=n;i++)
        cout<<cnt[i]<<" ";
    cout<<endl;*/
/*  for(int i=1;i<=n;i++){
        for(int j=1;j<=cnt[i];j++){
            cout<<s[i][j]<<" ";
        }
        cout<<endl;
    }*/

    int ans=-1e9;
    for(int i=1;i<=cnt[n];i++){
        for(int j=1;j<=cnt[n-1];j++){
            ans=max(ans,f[n][i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}