记录编号	124253	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]炮兵阵地	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.153 s
提交时间	2014-10-02 20:32:52	内存使用	1.79 MiB

#include<cstdio>
#include<iostream>
using namespace std;
int m,n,sum=0;
int v[101][61]={0};//v[i][j]存第i行,第j种状态;v[i][0]存第i行状态总数;
int dx[101][61]={0};//dx[i][j]与v[i][j]相对应,表示i行,第j种状态能放几个炮兵;
int fr[101][61][61]={0};//fr[i][m][n]表示前i行,第i行状态为n,第i-1行状态为m的最优解;
bool f[101][11]={0};//初始状态;
void dfs(int,int,int,int);
int main()
{
	freopen("cannon.in","r",stdin);
	freopen("cannon.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
	{
		char x;
		for(int j=1;j<=n;j++)
		{
			cin>>x;
			if(x=='P') f[i][j]=1;
		}
	}
	for(int i=1;i<=m;i++) dfs(i,1,0,0);
	for(int i=1;i<=v[1][0];i++)//因为炮兵的影响范围是两个格,所以要先对前两行进行预处理;
	{
		for(int j=1;j<=v[2][0];j++)
		{
			if(v[1][i]&v[2][j])	continue;//表示两行状态矛盾,炮兵可以互相攻击到;
			fr[2][i][j]=dx[1][i]+dx[2][j];
		}
	}
	for(int i=3;i<=m;i++)
	{
		for(int j=1;j<=v[i][0];j++)//枚举第i行状态;
		{
			for(int p=1;p<=v[i-1][0];p++)//枚举第i-1行状态;
			{
				if(v[i][j]&v[i-1][p]) continue;//i行与i-1行不能矛盾;
				for(int q=1;q<=v[i-2][0];q++)//枚举第i-2行状态;
				{
					if(v[i][j]&v[i-2][q]||v[i-1][p]&v[i-2][q]) continue;
					if(fr[i-1][q][p]+dx[i][j]>fr[i][p][j])//前i-1行能放炮兵的数目加上第i行某个状态能放炮兵的数目;
						fr[i][p][j]=fr[i-1][q][p]+dx[i][j];//比原来大就更新;
				}
			}
		}
	}
	for(int i=1;i<=v[m-1][0];i++)//寻找后两行最优解的最大值;
	{
		for(int j=1;j<=v[m][0];j++)
		{
			if(fr[m][i][j]>sum) sum=fr[m][i][j];
		}
	}
	if(m==1)//如果数据只有一行,那么上面的语句都不会执行,需要特殊判断;
	{
		for(int i=1;i<=dx[1][0];++i)
		{
			if(dx[1][i]>sum) sum=dx[1][i];
		}
	}
	printf("%d",sum);
	return 0;
}
void dfs(int i,int j,int k,int w)//第i行第j列,状态为w,炮兵数为k;
{
	if(j>n)
	{
		v[i][++v[i][0]]=w;
		dx[i][++dx[i][0]]=k;
		return;
	}
	dfs(i,j+1,k,w);//默认不放炮兵;
	if(f[i][j]) dfs(i,j+3,k+1,w|1<<(n-j));//放置炮兵,隔开两个格放置下一个;
}