记录编号	230597	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]炮兵阵地	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.492 s
提交时间	2016-02-22 13:28:07	内存使用	1.64 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

int n,m,i,j,c=2,dp[110][60][60]={0},r[110],ans=0,a,b;
//dp[i][j]表示前两行为tr[i]，tr[j]时的最多放置数 
bool g[110][11];
const int tr[60]={0,1,2,4,8,9,16,17,18,32,33,34,36,64,65,66,68,72,73,128,129,130,132,136,137,144,145,146,256,257,258,260,264,265,272,273,274,288,289,290,292,513,514,516,520,521,528,529,530,544,545,546,548,576,577,578,580,584,585,512};
//这个const int数组每一位代表这一行全为平原的可行方案的二进制转十进制数，可由简洁程序预处理获取 

int tran(int x)//解压整数x代表的bool数组中含有几个点 
{
	int i,answer=0;
	for (i=x;i!=0;i/=2) if (i%2==1) answer++;
	return answer;
}

int rar(bool *a)//压缩每行的bool数组 
{
	int i,x=0;
	for (i=0;i<m;i++) {if (a[i]) x+=1<<i;}
	return x;
}

int not_and(int x) {return (1<<m)-1-x;}

void extend(int c,int x,int y)
{
	int i,k=not_and(tr[x])&not_and(tr[y])&r[c+1];//k代表可行点的bool数组翻译码 
	//if (c==2&&x==0&&y==1) cout<<k<<endl;
	for (i=0;i<60;i++) if (tr[i]>=1<<m) break;else
	if ((tr[i]&k)==tr[i])//代表该方案可行 
		{
			//if (c==2&&x==0&&y==1) cout<<tr[i]<<" "<<tran(tr[i])<<endl;
			dp[c+1][y][i]=max(dp[c][x][y]+tran(tr[i]),dp[c+1][y][i]);
		}
	return;
}

int main()
{
	freopen("cannon.in","r",stdin);
	freopen("cannon.out","w",stdout);
	memset(g,1,sizeof(g));
	scanf("%d%d",&n,&m);
	char x;
	for(i=2;i<=n+1;i++){
		for(j=0;j<m;j++){
			cin>>x;if(x=='H') g[i][j]=0;
		}
	}
	for (i=0;i<=n+1;i++) r[i]=rar(g[i]);//翻译并压缩地图，以便下面的操作 
	for (c=1;c<=n;c++)
	  for (i=0;i<60;i++) if (tr[i]>=1<<m) break;else
	    for (j=0;j<60;j++) if (tr[j]>=1<<m) break;else
		  extend(c,i,j);
	for (c=2;c<=n+1;c++)
	  for (i=0;i<60;i++) if (tr[i]>=1<<m) break;else
	    for (j=0;j<60;j++) if (tr[j]>=1<<m) break;else{
	    	//printf("%d %d %d %d\n",c,tr[i],tr[j],dp[c][i][j]);
	    	ans=max(ans,dp[c][i][j]);
		}
	printf("%d\n",ans);
	return 0;
}