POJ 炮兵阵地 (状态压缩dp)

真的很难，状态转移方程太难推了，智商不够，努力来凑

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 1e2+10;
int dp[maxn][maxn][maxn],cur[maxn],stk[maxn<<6],top,num[maxn];
char map[maxn][maxn];
int m,n;
inline bool ok(int x)
{
	if(x&(x<<1)) return 0;
	if(x&(x<<2)) return 0;
	return 1;
}
inline int cnt(int x)
{
	int s = 0;
	while(x){ s++; x = x&(x-1);}
	return s;	
} 
inline int fit(int x,int k)
{
	if(cur[k]&x) return 0;
	return 1;
}
int main()
{
	while(~scanf("%d%d",&m,&n)&&m*n)
	{
		top = 0;
		int tot = (1<<n);
		for(int i = 0; i < tot; ++i)
		if(ok(i)) stk[++top] = i;       //初始化一行可以拥有的所有二进制状态 
		for(int i = 1; i <= m; ++i) scanf("%s",map[i]+1); //输入 
		for(int i = 1; i <= m; ++i)
		{
			cur[i] = 0;
			for(int j = 1; j <= n; ++j)
			if(map[i][j]=='H') cur[i]+=(1<<(j-1)); //计算当前行的二进制状态 
		}
		memset(dp,-1,sizeof(dp));
		for(int i = 1; i <= top; ++i)
		{
			num[i] = cnt(stk[i]);
			if(fit(stk[i],1)) dp[1][1][i] = num[i]; //初始化第一行状态 
		}
		for(int i = 2; i <= m; ++i)
		{
			for(int t = 1; t <= top; ++t)
			{
				if(fit(stk[t],i)==0) continue; //第i行状态为t 
				for(int j = 1; j <= top; ++j)
				{
					if(stk[j]&stk[t]) continue; //第i-2行状态不能跟i行冲突 
					for(int k = 1; k <= top; ++k)
					{
						if(stk[k]&stk[t]) continue; //第i-1行状态也不能跟i行状态冲突 
						if(dp[i-1][j][k]==-1) continue; // 第i-1行状态存在的话才递推 
						dp[i][k][t] = max(dp[i][k][t],dp[i-1][j][k]+num[t]);
					}
					
				}
			}
		}
		int ans = 0;
		for(int i = 1; i <= m; ++i)
			for(int j = 1; j <= top; ++j)
				for(int k = 1; k <= top; ++k)
					ans = max(ans,dp[i][j][k]);
		printf("%d\n",ans);		
		
	}	
}