记录编号	332333	评测结果	AWAWWWWWWW
题目名称	[NOI 2001]炮兵阵地	最终得分	20
用户昵称	LOSER	是否通过	未通过
代码语言	C++	运行时间	0.926 s
提交时间	2016-10-28 18:39:58	内存使用	67.51 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 110
#define maxm 1030
using namespace std;
int n,m,a[maxn][maxn],can[maxm],used[maxm],S,size,f[maxn][400][400],mp[maxn];
bool Canuse(int i,int j,int k){
	if(((can[i]|can[j])&can[k])==0)return 1;
	return 0;
}
bool Match(int id,int s){
	if((mp[id]|can[s])==mp[id])return 1;
	return 0;
}
int main(){
	freopen("cannon.in","r",stdin);freopen("cannon.out","w",stdout);
	scanf("%d%d",&n,&m);
	char s[maxn];
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		for(int j=0;j<m;j++) if(s[j]=='P') mp[i]|=(1<<j);
	}
	bool flag;
	int pos,sumt;
	S=1<<m;
	for(int i=0;i<S;i++){
		flag=0;pos=-1;sumt=0;
		for(int j=0;j<m;j++){
			if(i&(1<<j)){
				sumt++;
				if(pos>=0&&j-pos<=2)flag=1;
				pos=j;
			}
		}
		if(!flag)can[++size]=i,used[size]=sumt;
	}
	//printf("size=%d\n",size);
	for(int i=1;i<=size;i++)if(Match(1,i))f[1][i][0]=used[i];
	int s1,s2,s3;
	for(int id=2;id<=n;id++){
		for(int i=1;i<=size;i++){
			for(int j=1;j<=size;j++){
				//if(f[id-1][j][i])
				for(int k=1;k<=size;k++){
					if(Canuse(i,j,k) && (mp[id]|can[k]==mp[id])){
						f[id][k][j]=max(f[id][k][j],f[id-1][j][i]+used[k]);
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=size;i++){
		for(int j=1;j<=size;j++){
			if(!Match(n-1,i)||!Match(n,j))continue;
			ans=max(ans,f[n][j][i]);
		}
	}
	printf("%d\n",ans);
	getchar();getchar();
	return 0;
}