记录编号	84220	评测结果	WWAAAAAAWA
题目名称	[NOI 2001]炮兵阵地	最终得分	70
用户昵称	二价氢	是否通过	未通过
代码语言	C++	运行时间	0.159 s
提交时间	2013-12-10 19:40:53	内存使用	1.75 MiB

#include <iostream>
#include <cstdio>
using namespace std;
int MAP[120];
int dp[105][60][60];
int AP[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,512,513,514,516,
520,521,528,529,530,
544,545,546,548,576,
577,578,580,584,585};
int cn[60]={
0,1,1,1,1,2,
1,2,2,1,2,2,
2,1,2,2,2,2,
3,1,2,2,2,2,
3,2,3,3,1,2,
2,2,2,3,2,3,
3,2,3,3,3,1,
2,2,2,2,3,2,
3,3,2,3,3,3,
2,3,3,3,3,4};
int totavail=60;
int M,N;
int Kmax(int x,int y)
{
	return (x>y)?x:y;
}
int count(int x)
{
	int ans=0;
	while (x)
	{
		if (x&1)
			ans++;
		x>>=1;
	}
	return ans;
}
void Kdp()
{
	for (int i=2;i<=N+1;i++)
	{
		for (int j=0;j<totavail;j++)
		{
			if (AP[j]&MAP[i-2])
				continue;
			for (int k=0;k<totavail;k++)
			{
				if (AP[k]&MAP[i-1])
					continue;
				if (AP[k]&AP[j])
					continue;
				for (int l=0;l<totavail;l++)
				{
					//cout<<i<<' '<<j<<' '<<k<<' '<<l<<endl;
					if (AP[l]&MAP[i])
						continue;
					if (AP[k]&AP[l])
						continue;
					if (AP[j]&AP[l])
						continue;
					dp[i][l][k]=max(dp[i][l][k],dp[i-1][k][j]+cn[l]);
				}
			}
		}
	}
}
int main()
{
	freopen("cannon.in","r",stdin);
	freopen("cannon.out","w",stdout);
	int ans=0;
	char tmp;
	cin>>N>>M;
	for (int i=2;i<=N+1;i++)
		for (int j=1;j<=M;j++)
		{
			MAP[i]*=2;
			cin>>tmp;
			if (tmp=='H')
				MAP[i]+=1;
		}
	Kdp();
	for (int i=0;i<totavail;i++)
		for (int j=0;j<totavail;j++)
			ans=Kmax(ans,dp[(N+1)][i][j]);
	cout<<ans<<endl;
	return 0;
}