记录编号	532415	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]炮兵阵地	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.426 s
提交时间	2019-05-29 12:55:58	内存使用	17.94 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=101;
int state[N],tot,n,m,cnt,p[N],ans;
int F[110],dp[110][N][N];
void init()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		char s[12];
		scanf("%s",s);
		for (int j=1;j<=m;j++)
		F[i]=(F[i]<<1)+(s[j-1]=='H');
	}
	tot=(1<<m)-1;
	for (int i=0;i<=tot;i++)
	{
		if (!((i<<1)&i)&&!((i<<2)&i))
		{
			cnt++;
			state[cnt]=i;
			int t=i;
			while (t)
			{
				p[cnt]+=t&1;
				t>>=1;
			}
		}
	}
}
int main()
{
	freopen("cannon.in","r",stdin);
	freopen("cannon.out","w",stdout); 
	init();
	for (int i=1;i<=cnt;i++)
	 for (int j=1;j<=cnt;j++)
	{
		if (!(state[i]&state[j])&&!(state[i]&F[2])&&!(state[j]&F[1]))
		dp[2][i][j]=p[j]+p[i];
	}
	for (int i=3;i<=n;i++)
	{
		for (int j=1;j<=cnt;j++)//当前行状态 
		{
			if (!(state[j]&F[i]))
			{
				for (int k=1;k<=cnt;k++)//上一行状态 
				{
					if (!(state[k]&F[i-1])&&!(state[k]&state[j]))
					{
						for (int q=1;q<=cnt;q++)//上两行状态 
						{
							if (!(state[q]&F[i-2])&&!(state[q]&state[k])&&!(state[q]&state[j]))
							{
								dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][q]+p[j]);
								ans=max(ans,dp[i][j][k]); 
							}
						}
					}
				}
			}
		}
	}
	printf("%d",ans);
	return 0; 
}