记录编号	174116	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]炮兵阵地	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.177 s
提交时间	2015-07-31 11:57:34	内存使用	1.73 MiB

#include<cstdio>
using namespace std;
int n,m,maxl,state[111][61],shu[111],num[111][61],f[111][61][61];
bool p[111][11];
char c;
void dfs(int i,int sb,int sum,int stat)
{
    state[i][++shu[i]]=stat;
    num[i][shu[i]]=sum;
    for(sb+=3;sb<=m;++sb)
        if(p[i][sb])
            dfs(i,sb,sum+1,stat|(1<<(sb-1)));
}
int main()
{
    freopen("cannon.in","r",stdin);
    freopen("cannon.out","w",stdout);
	scanf("%d%d",&n,&m);
	getchar();
	for(int i=1;i<=n;++i)
	{
	    for(int j=1;j<=m;++j)
	    {
			c=getchar();
			if(c=='P')
				p[i][j]=1;
		}
	    getchar();
	}
	for(int i=1;i<=n;++i)
	    for(int j=1;j<=m;++j)
	        if(p[i][j])
	            dfs(i,j,1,1<<(j-1));
    for(int i=0;i<=shu[1];++i)
        for(int j=0;j<=shu[2];++j)
            if(!(state[1][i]&state[2][j]))
                f[2][j][i]=num[1][i]+num[2][j];
	for(int i=3;i<=n;++i)
		for(int j=0;j<=shu[i];++j)//i
            for(int k=0;k<=shu[i-1];++k)//i-1
                if(!(state[i][j]&state[i-1][k]))
                    for(int q=0;q<=shu[i-2];++q)//i-2
                        if(!(state[i][j]&state[i-2][q])&&!(state[i-1][k]&state[i-2][q])&&f[i][j][k]<f[i-1][k][q]+num[i][j])
                        {
                            f[i][j][k]=f[i-1][k][q]+num[i][j];
                            if(maxl<f[i][j][k])
                                maxl=f[i][j][k];
                        }
	//printf("f[%d][%d]=%d\n",i,state[i][j],f[i][state[i][j]]);
    printf("%d",maxl);
	//while(1);
}