花了好久理解了这种做法。
这里用到了很多压缩，首先，预处理出每行所有可行的状态，因为一行之中，可行的状态就是每两个炮兵之间间隔2以上，所以只要简单的移位运算就可以处理出来。
然后记录每种状态炮兵的数量，我们用1表示这里有炮兵0表示没有，那么这种状态的炮兵数量就是二进制1的个数，很好处理。
接下来对于每行的图，也进行压缩，将不可以放置炮兵的地方用1表示，那么用来判断这个位置是否可以放置炮兵的时候就可以使用位运算来简单的操作了。
下面对一些变量进行一下解释：
Count[i]:表示这第i状态的炮兵数量。
st[i]:表示第i状态。1表示有炮兵，0表示没炮兵。
MM[i]:表示第i行压缩后的地图。用1表示不可放置，0表示可放置。
dp[i][j][k]:表示i行，当前状态是k,上一行状态是j,总的可行方案。
对于每个状态的转移，假设当前状态是k,上一状态是j,那么首先判断这两个状态是否会互相攻击，即（st[k] & st[j]），然后判断该行是否可以放置这个状态。即（MM[i] & st[k]） ,还要判断上一状态是否可以放到i - 1行，即（MM[i - 1] & st[j]） .
然后枚举上上状态l,同样判断是否合法。那么首先判断i - 2 行是否可以放置状态l,即（MM[i - 2] & st[l]） ,然后是上上状态是否和当前状态，上一状态互相攻击，即（st[j] & st[l] ） , （st[k] & st[l]）。
这样判断之后，那么k状态就可以由j 和 l状态推过来，那么更新该状态即可。
状态转移方程：dp[i][j][k] = max（dp[i][j][k] , dp[i - 1][l][j] + Count[k]） ;
int st[111] ;//每行所有的可行的状态
int top = 0 ;
int Count[111] ;//每个状态对应的个数
int n , m ;
char Map[111][15] ;
int dp[111][65][65] ;//dp[i][j][k] .第i行状态是k, i - 1 行状态是j的可行总数
int MM[111] ;//压缩地图
void init（） {
top = 0 ;
mem（st ,0） ;
mem（Count ,0） ;
mem（dp ,0） ;
mem（MM ,0） ;
}
void isok（） {//计算出每行所有可行的状态数。
for （int i = 0 ; i < 1 《 m ; i ++ ） {
if（（i & （i 《 1））|| （i & （i 《 2）））continue ;
int tt = i ;
int nn = 0 ;
while（tt） {
nn += tt % 2 ;
tt /= 2 ;
}
Count[top] = nn ;
st[top ++ ] = i ;
}
}
int main（） {
cin 》 n 》 m ;
init（） ;
for （int i = 1 ; i <= n ; i ++ ） {
scanf（"%s",Map[i]） ;
for （int j = 0 ; j < m ; j ++ ） {
if（Map[i][j] == 'H'）MM[i] += （1 《 j） ;
}
}
isok（） ;
//第一行
int ans = 0 ;
for （int i = 0 ; i < top ; i ++ ） {
if（st[i] & MM ） continue ;
dp [0][i] = Count[i] ;//第1行所有可行的状态。
ans = max（ans ,dp [0][i]） ;
}
for （int i = 2 ; i <= n ; i ++ ） { //当前行
for （int j = 0 ; j < top ; j ++ ） { //上一状态
for （int k = 0 ; k < top ; k ++ ） { //当前状态
if（st[k] & MM[i] || st[j] & st[k] || MM[i - 1] & st[j]）continue ;
for （int l = 0 ; l < top ; l ++ ） { //上上状态
if（st[j] & st[l] || st[l] & st[k] || st[l] & MM[i - 2] || !dp[i - 1][l][j]）continue ;
dp[i][j][k] = max（dp[i][j][k] , dp[i - 1][l][j] + Count[k]） ;
ans = max（ans , dp[i][j][k]） ;
}
}
}
}
printf（"%d\n",ans） ;
return 0 ;
}
HDU 3853 求期望 --8.16
http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html
这个博客不错，总结的很好。
求概率一般是从前往后推，求期望一般是从后往前推。
这道题加了优化300MS,不加优化4000MS,差点超时。
#define N 1005
int n , m ;
double dp[N][N] ;
struct M{
double p ;
}MM[N][N] ;
int main（） {
while（cin 》 n 》 m）{
for （int i = 1 ; i <= n ; i ++ ）{
for （int j = 1 ; j <= m ; j ++ ）{
dp[i][j] = 0 ;
for （int k = 0 ; k < 3 ; k ++ ）{
RD（MM[i][j].p[k]） ;
}
}
}
for （int i = n ; i >= 1 ; i -- ）{
for （int j = m ; j >= 1 ; j -- ）{
if（i == n && j == m）continue ;
double xx = 1 - MM[i][j].p[0] ;
if（xx < 1e-5）continue ;
dp[i][j] = dp[i + 1][j] * （ MM[i][j].p / xx ） + dp[i][j + 1] * （ MM[i][j].p / xx ） + 2 / xx ;
}
}
printf（"%.3f\n",dp ） ;
}
return 0 ;
}