90分代码:

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,dp[N][N][N],mp[N],cnt;
struct P{
	int s,num;
}a[N];
char ch;
void pre();
void clean();
int MAX;
int main(){
	clean();
	scanf("%d%d",&n,&m);
	MAX=1<<m;
	getchar();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%c",&ch);
			mp[i]=mp[i]<<1;
			if(ch=='P'){
				mp[i]+=1;
			}else{
				mp[i]+=0;
			}
		}
		getchar();
	}
	pre();
	for(int i=3;i<=n;i++){
		for(int j=1;j<=cnt;j++){
			if((mp[i]&a[j].s)==a[j].s){
				for(int k=1;k<=cnt;k++){
					if(!(a[j].s&a[k].s)){
						for(int z=1;z<=cnt;z++){
							if((!(a[k].s&a[z].s))&&(!(a[j].s&a[z].s))){
								dp[i][k][j]=max(dp[i][k][j],dp[i-1][z][k]+a[j].num);
							}
						}
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=cnt;j++){
			ans=max(ans,dp[n][i][j]);
		}
	}
	printf("%d",ans);
	return 0;
}
void pre(){
	for(int i=0;i<MAX;i++){
		if((i&(i<<1))||(i&(i<<2))||(i&(i>>1))||(i&(i>>2))){
			continue;
		}
		cnt++;
		a[cnt].s=i;
		for(int j=0;(1<<j)<=i;j++){
			a[cnt].num+=!!(i&(1<<j));
		}
		if((i&mp[1])==i){
			dp[1][0][cnt]=a[cnt].num;
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=cnt;j++){
			if((!(a[i].s&a[j].s))&&(mp[2]&a[j].s)==a[j].s){
				dp[2][i][j]=dp[1][0][i]+a[j].num;
			}
		}
	}
}
void clean(){
	memset(a,0,sizeof(a));
	memset(dp,0,sizeof(dp));
	memset(mp,0,sizeof(mp));
	n=m=cnt=0;
}

#1数据为样例数据

该代码在本地及敝校OJ运行结果为正确答案(6),但在洛谷测评姬及在线IDE上结果为5.

求解答(轻喷)