记录编号	174216	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]炮兵阵地	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.242 s
提交时间	2015-07-31 18:13:23	内存使用	4.61 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int map[102],num[(1<<10)-1];
int z[1200];
bool q[102][15];
int f[102][105][105];//一开始开了两维，总输出8； 
int n,m,ans,tot;
inline bool ok(int x,int y){
	if(z[x]&map[y])
	   return 0;
	return 1;
}
int sd(int y){
	int sum=0;
	while(y){
		if(y>0){
			if(y&1)
			  sum++;
			y>>=1;
		}
	}
	return sum;
}
int main(){
	freopen("cannon.in","r",stdin);
	freopen("cannon.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		char x;
		for(int j=1;j<=m;++j){
			cin>>x;
			if(x=='H')
			 {
			    map[i]+=(1<<(j-1));
			 }
		}
	}
	 for(int x=0;x<(1<<m);++x){
	 	if((x&(x<<1))||(x&(x<<2)))
	 	  continue;
	 	else
	 	  {
	 	  	z[++tot]=x;
	 	  	num[x]=sd(x);
	 	  }
	 }
	 for(int i=1;i<=tot;++i)
	   if(ok(i,1))
	      {
	      	f[1][i][0]=num[z[i]];
	      }
	 for(int j=1;j<=tot;++j){
	 	if(ok(j,2)){
	 		for(int k=1;k<=tot;++k){
	 			if(ok(k,1)){
	 				if(!(z[j]&z[k])){
	 					{
						   f[2][j][k]=max(f[2][j][k],f[1][k][0]+num[z[j]]);
	 					}
	 				}
	 			}
	 		}
	 	}
	 }
	 for(int i=3;i<=n;++i)
	   for(int j=1;j<=tot;++j){
	   	 if(ok(j,i)){
	   	 	for(int k=1;k<=tot;++k){
	   	 		if(ok(k,i-1)){
	   	 			for(int h=1;h<=tot;++h){
	   	 				if(ok(h,i-2)){
	   	 					if((!(z[h]&z[k])&&(!(z[k]&z[j]))&&(!(z[h]&z[j])))){
	   	 						f[i][j][k]=max(f[i][j][k],f[i-1][k][h]+num[z[j]]);
	   	 					}
	   	 				}
	   	 			}
	   	 		}
	   	 	}
	   	 }
	   }
	   if(n==1){
	   	for(int i=1;i<=n;++i)
	   	 ans=max(ans,f[1][i][0]);
	   }
	   for(int k=1;k<=tot;++k)
	   for(int i=1;i<=tot;++i){
	   	  ans=max(ans,f[n][k][i]);
	   }
	   printf("%d",ans);
	  // while(1);
}