题目：http://poj.org/problem?id=1185
大神的题解：
方法就是用DP[i][r][p]表示第i行状态为r，第i-1行状态是p时的最多个数。而这里p受到r的限制，而第i-2行状态q则受到r和p两个状态限制。状态转移方程就是：
DP[i][r][p] = MAX{DP[i-1][p][q] +num[r]}
其中，p是受到r的限制时枚举的状态，q是受到r和p共同限制时候的状态，num[r]表示状态r里面的布局炮兵所摆的个数。
这里我们可以看到就要枚举i，r，p，q,这4 个变量，i的范围是100，而其他几个则都是1<<10,复杂度颇为偏高。而实际上由于每一行里面有很多都是某些位置被其他位置影响的。比如： 1110001， 如果第一个位置放上炮兵，那么第二第三的位置都会受到影响，而一个也放不了。
解决方案就是不去管那些相互有影响的状态，把形如：
1000000 0100000 ... ...
1001000 0100001 ... ...
...
1001001
这些相互之间没有影响的状态找出来，这样所有的状态数就会减少至少于60种（我算了一下，好像是58种），这样一来就是60*60*60*100，可以过了。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define mod 100000000
using namespace std;
int m,n,top,state[],cur[],num[],dp[][][];
char tu[][];
inline bool ok(int x)
{
if(x&(x<<)) return false;
if(x&(x<<)) return false;
return true;
}
inline void init()
{
int tol=<<n;
top=;
for(int i=; i<tol; i++)
{
if(ok(i)) state[++top]=i;
}
}
inline bool fit(int x,int k)
{
if(x&cur[k]) return false;
return true;
}
inline int icount(int x)
{
int cnt=;
while(x)
{
cnt++;
x=x&(x-);
}
return cnt;
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
init();
for(int i=; i<=m; i++)
scanf("%s",tu[i]+);
for(int i=;i<=m;i++)
{
cur[i]=;
for(int j=;j<=n;j++)
{
if(tu[i][j]=='H')
cur[i]+=(<<(n-j));
}
}
memset(dp,,sizeof(dp));
for(int i=; i<=top; i++)
{
num[i]=icount(state[i]);
if(fit(state[i],))
dp[][][i]=num[i];
}
for(int i=; i<=m; i++)
{
for(int t=; t<=top; t++)
{
if(!fit(state[t],i)) continue;//符合本行
for(int j=; j<=top; j++)
{
if(state[j]&state[t]) continue;//符合上一行
for(int k=; k<=top; k++) //符合上上行
{
if(state[k]&state[t]) continue;
if(state[k]&state[j]) continue;
dp[i][j][t]=max(dp[i][j][t],(dp[i-][k][j]+num[t]));
}
}
}
}
int maxx=-;
for(int i=; i<=m; i++)
{
for(int j=; j<=top; j++)
{
for(int k=; k<=top; k++)
{
maxx=max(maxx,dp[i][j][k]);
}
}
}
printf("%d\n",maxx);
}
return ;
}