记录编号	412676	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]炮兵阵地	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	0.151 s
提交时间	2017-06-09 20:11:13	内存使用	5.48 MiB

#include<iostream>
#include<cstdio>

using namespace std;

char ma[110][20];
int n,m,s[110][110],sc[110],num[110][110];
int f[110][110][110];

void dfs(int lie,int hang,int zt,int cnt,int efc)
{
	if(lie==m+1)
	{
		s[hang][++sc[hang]]=zt;
		num[hang][sc[hang]]=cnt;
		return;
	}
	if(ma[hang][lie]=='P')
	{
		dfs(lie+1,hang,zt<<1,cnt,efc+1);
		if(efc>=2) dfs(lie+1,hang,(zt<<1)+1,cnt+1,0);
	}
	else
	{
		dfs(lie+1,hang,zt<<1,cnt,efc+1);
	}
}

int main()
{
	freopen("cannon.in","r",stdin);
	freopen("cannon.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	 {
	 	cin>>ma[i][j];
	 }
	for(int i=1;i<=n;i++)
	{
		dfs(1,i,0,0,2);
	}
	for(int i=1;i<=sc[1];i++)
	{
		f[1][i][0]=num[1][i];
	}
	for(int i=1;i<=sc[2];i++)
	 for(int j=1;j<=sc[1];j++)
	{
		if(s[2][i]&s[1][j]) continue;
		f[2][i][j]=max(f[2][i][j],f[1][j][0]+num[2][i]);
	}
	for(int i=3;i<=n;i++)
	 for(int k=1;k<=sc[i];k++)
	  for(int l=1;l<=sc[i-1];l++)
	   for(int j=1;j<=sc[i-2];j++)
	   {
	   		if((s[i][k]&s[i-1][l])||(s[i][k]&s[i-2][j])||(s[i-1][l]&s[i-2][j])) continue;
	   		f[i][k][l]=max(f[i][k][l],f[i-1][l][j]+num[i][k]);
	   }
	int ans=-1e9;
	for(int i=1;i<=sc[n];i++)
	 for(int j=1;j<=sc[n-1];j++)
	 {
		ans=max(ans,f[n][i][j]);
	 }
	printf("%d",ans);
	return 0;
}