萌新刚学 OI ，在线求助状压dp 10pts

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200;
int n,m,init[150],full,tot,s[N],cnt[N];
int f[150][N][N],ans;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
bool check(int x){
    if(x&(x>>2)) return 0;
    if(x&(x<<2)) return 0;
    if(x&(x<<1)) return 0;
    if(x&(x>>1)) return 0;
    return 1;
}
int count(int x){
    int res=0;
    while(x){
    if(x&1) res++;
    x>>=1;
    }
    return res;
}
signed main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        char c;
        cin>>c;
        if(c=='P') init[i]=(init[i]<<1)+1;//可放置的二进制表示
        else init[i]=(init[i]<<1)+0;
    }
    }
    full=(1<<m)-1;
    for(int i=0;i<=full;i++){
    if(check(i)){
        s[++tot]=i;
        cnt[tot]=count(i);
    }
    }
    for(int i=1;i<=tot;i++)
    if((s[i]&init[1])==s[i]) f[1][i][0]=cnt[i];
    for(int i=1;i<=tot;i++){
    if((s[i]&init[2])==s[i])
        for(int j=1;j<=tot;j++){
        if((s[i]&s[j])==0&&(s[j]&init[1])==s[j])
            f[2][i][j]=cnt[j]+cnt[i];
        }
    }
    for(int i=3;i<=n;i++)
    for(int j=1;j<=tot;j++)
        if((s[j]&init[i])==s[j])
        for(int k=1;k<=tot;k++)
            if((s[j]&s[k])==0&&(s[k]&init[i-1])==s[k])
            for(int z=1;z<=tot;z++)
                if((s[j]&s[z])==0&&(s[k]&s[z])==0&&(s[z]&init[i-2])==s[z])
                f[i][j][z]=max(f[i][j][z],f[i-1][k][z]+cnt[j]);
    for(int i=1;i<=tot;i++)
    for(int j=1;j<=tot;j++)
        ans=max(ans,f[n][i][j]);
    printf("%lld",ans);
    return 0;
}