WA on#7 90pts

OutsideR_ @ 2024-04-11 13:24:14

by OutsideR_ @ 2024-04-11 13:24:24

#include <iostream>
using namespace std;
int n,m;
char a[105][15];
int dp[2050][2050][105]; 
int hefa[2050],h=1;
int ban[2050];
int one[2050];
int ans=0;
int got(int x){
    int t=0;
    while(x){
        if(x&1){
            t++;
        }
        x>>=1;
    }
    return t;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='P'){
                ban[i]=ban[i]|(1<<j); 
            }
        }
    }
    for(int f=1;f<(1<<(m+1));f++){
        if(f&1==1)continue;
        if((((f>>1)|(f<<1)|(f>>2)|(f<<2))&f)==0){
            hefa[h]=f;
            one[h]=got(f);
            if((f&ban[1])==f){
                dp[1][f][1]+=one[h];
                ans=max(ans,dp[1][f][1]);
            }
            h++;
        }
    }
    if(n==1){
        cout<<ans<<endl;
        return 0;
    }
    if(n>=2){
        for(int i=1;i<h;i++){
            int f1=hefa[i];
            if((f1&ban[2])!=f1)continue;
            for(int j=1;j<h;j++){
                int f2=hefa[j];
                if((i==j) || (f2&ban[1])!=f2)continue;
                if((f1&f2)!=0)continue;
                dp[f2][f1][2]=max(dp[f2][f1][2],dp[1][f2][1]+one[i]);
                ans=max(ans,dp[f2][f1][2]);
            }
        }
        if(n==2){
            cout<<ans<<endl;
            return 0;
        } 
    }
    if(n>2){
        for(int mm=3;mm<=n;mm++){
            for(int i=1;i<h;i++){
                int f1=hefa[i];
                if((f1&ban[mm])!=f1)continue;
                for(int j=1;j<h;j++){
                    int f2=hefa[j];
                    if((i==j) || (f2&ban[mm-1])!=f2)continue;
                    if((f1&f2)!=0)continue;
                    for(int k=1;k<h;k++){
                        int f3=hefa[k];
                        if((k==j) || (k==i) || (f3&ban[mm-2])!=f3)continue;
                        if((f3&f2)!=0)continue;
                        if((f3&f1)!=0)continue;
                        dp[f2][f1][mm]=max(dp[f2][f1][mm],dp[f3][f2][mm-1]+one[i]);
                        ans=max(ans,dp[f2][f1][mm]);
                    }
                }
            }
        }
        cout<<ans<<endl;
        return 0;
    }
}