蒟蒻求助

70分，7AC3WA

#include<bits/stdc++.h>
using namespace std;
int d[120],f[120][1050][1050],need[1050],ans,maxstate,n,m;
bool can[1050];
char ch;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch;
            if(ch=='P')d[i]=d[i]<<1;
            else d[i]=d[i]<<1|1;
        }
    }
    maxstate=(1<<m)-1;
    for(int i=0;i<=maxstate;i++){
        if(((i<<2)&i)==0&&((i<<1)&i)==0){
            can[i]=true;
            int u=i;
            while(u){
                if(u&1)need[i]++;
                u>>=1;
            }
            if((i&d[i])==0) f[1][0][i]=need[i];
        }
    }
    for(int i=0;i<=maxstate;i++){
        if(can[i]&&(i&d[1])==0){
            for(int j=0;j<=maxstate;j++){
                if((i&j)==0&&can[j]&&(j&d[2])==0){
                    f[2][i][j]=max(f[1][0][i]+need[j],f[2][i][j]);
                }
            }
        }
    }
    for(int i=3;i<=n;i++){
        for(int j=0;j<=maxstate;j++){
            if(can[j]&&(d[i]&j)==0){
                for(int l=0;l<=maxstate;l++){
                    if((l&j)==0&&can[l]){
                        for(int h=0;h<=maxstate;h++){
                            if((l&h)==0&&(j&h)==0&&can[h]){
                                f[i][j][l]=max(f[i][j][l],f[i-1][l][h]+need[j]);
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<=maxstate;i++){
        if(can[i]){
            for(int j=0;j<=maxstate;j++){
                if(can[j])ans=max(ans,f[n][i][j]);
            }
        }

    }
    cout<<ans;
}