思路：定义一个三维数组dp[x][i][j]其中x为now和pre两种状态，now表示当前两行最优解，pre表示出了本行外，前两行的最优解。那么状态转移方程为
dp[now][j][k]=max(dp[now][j][k],dp[pre][k][r]+num[i][j][1])。num[i][j][1]表示第i行的第j个状态的1的个数。转移条件是!(num[i][j][0]&num[i-1][k][0])&&!(num[i][j][0]&num[i-2][r][0])&&!(num[i-1][k][0]&num[i-2][r][0])为真。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define Maxn 1010
using namespace std;
int dp[][Maxn][Maxn],now,pre,num[][Maxn][],cnt1,cnt2,cnt3,graphic[][],n,m;
void dfs(int u,int j,int f)
{
int i;
if(j==m)
{
int sum,cc;
sum=cc=;
for(i=m;i>=;i--)
{
sum+=graphic[u][i]*(<<(m-i));
if(graphic[u][i])
cc++;
}
if(f<=)
{
if(graphic[u][j])
{
if(sum!=)
{
num[u][++cnt1][]=sum-;
num[u][cnt1][]=cc-;
}
}
else
{
num[u][++cnt1][]=sum;
num[u][cnt1][]=cc;
}
}
else
{
if(graphic[u][j])
{
if(sum!=)
{
num[u][++cnt1][]=sum-;
num[u][cnt1][]=cc-;
}
num[u][++cnt1][]=sum;
num[u][cnt1][]=cc;
}
else
{
num[u][++cnt1][]=sum;
num[u][cnt1][]=cc;
}
}
return ;
}
if(f<=)
{
if(graphic[u][j]==)
{
graphic[u][j]=;
dfs(u,j+,f+);
graphic[u][j]=;
}
else
dfs(u,j+,f+);
}
else
{
if(graphic[u][j])
{
dfs(u,j+,);
graphic[u][j]=;
dfs(u,j+,f+);
graphic[u][j]=;
}
else
dfs(u,j+,f+);
}
}
void out(int x)
{
if(x==||x==)
{
printf("%d",x);
return ;
}
int temp=x%;
out(x/);
printf("%d",temp);
}
int main()
{
int i,j,k,r;
char str[];
memset(graphic,,sizeof(graphic));
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,,sizeof(dp));
memset(num,,sizeof(num));
memset(graphic,,sizeof(graphic));
for(i=;i<=n;i++)
{
scanf("%s",&str);
for(j=;j<m;j++)
{
if(str[j]=='P')
graphic[i][j+]=;
else
graphic[i][j+]=;
}
}
dfs(,,);
cnt2=cnt1;
cnt1=;
dfs(,,);
now=,pre=;
for(i=;i<=cnt2;i++)
for(j=;j<=cnt1;j++)
{
if(!(num[][i][]&num[][j][]))
dp[now][j][i]=num[][i][]+num[][j][];
}
for(i=;i<=n;i++)
{
cnt3=cnt2,cnt2=cnt1,cnt1=;
dfs(i,,);
now=!now,pre=!pre;
for(j=;j<=cnt1;j++)
for(k=;k<=cnt2;k++)
for(r=;r<=cnt3;r++)
{
if(!(num[i][j][]&num[i-][k][])&&!(num[i][j][]&num[i-][r][])&&!(num[i-][k][]&num[i-][r][]))
dp[now][j][k]=max(dp[now][j][k],dp[pre][k][r]+num[i][j][]);
}
}
int ans=;
for(i=;i<=cnt1;i++)
for(j=;j<=cnt2;j++)
{
ans=max(ans,dp[now][i][j]);
}
printf("%d\n",ans);
}
return ;
}