状态压缩，看了周伟的动态规划之状态压缩，讲解的很详细，从写程序，到ac花了7个小时，3个小时敲代码，并理思路，4个小时调错，最后发现还是粗心问题，算法上病没有错误，不能在等啦，以后wa后，先仔细把代码看一遍，要有耐心呢，不能过度依赖调试，可能后者会浪费更多的时间
#include <iostream>
#include <cstdio>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
char g[100+10][10+10];
int c[65];
int f[100+10][65][65];
int s[65];
int cm[100+10];
int n,m;
int main()
{
while(~scanf("%d%d",&n,&m))
{
getchar();
int i,j,k,p;
memset(cm,0,sizeof(cm));
memset(f,0,sizeof(f));
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%c",&g[i][j]);
if(g[i][j]=='P') cm[i+1]|=(1<<j);
}
getchar();
}
int tot=0,t,tem,d,amount;
for(i=0;i<(1<<m);i++)
{
tem=-3;amount=0;
for(j=0;j<m;j++)
{
t=i&(1<<j);
if(t)
{
if((j-tem)<=2) break;
amount++;
tem=j;
}
}
if(j==m)
{
s[tot]=i;
c[tot++]=amount;
}
}
for(i=0;i<tot;i++)
{
for(j=0;j<tot;j++)
if((cm[1]&s[i])==s[i]) f[1][i][j]=c[i];
}
cm[0]=0;
for(i=2;i<=n;i++)
{
for(j=tot-1;j>=0;j--)
{
if((cm[i]&s[j])==s[j])
{
for(k=tot-1;k>=0;k--)
{
if((cm[i-1]&s[k])==s[k]&&!(s[j]&s[k]))
{
for(p=tot-1;p>=0;p--)
{
if(!(i-2)||(cm[i-2]&s[p])==s[p]&&!(s[k]&s[p])&&!(s[j]&s[p]))
{
f[i][j][k]=max(f[i-1][k][p]+c[j],f[i][j][k]);
}
}
}
}
}
}
}
int maxv=-1;
for(i=0;i<tot;i++)
{
for(j=0;j<tot;j++)
{
if(!(s[i]&s[j])) maxv=max(maxv,f[n][i][j]);
}
}
printf("%d\n",maxv);
}
return 0;
}