因为不知道不同的博客怎么转，就把别人的复制过来了，这个题解写的非常好，原地址为：
http://hi.baidu.com/wangxustf/item/9138f80ce2292b8903ce1bc7
分类：DP
题目分析与算法模型
因为行N <= 100 列M <= 10
我们就在10上面做文章。
在任意一行上，最多10列，假设这10个位置都是平原，那么在这10个位置上放置炮兵并互不攻击，一共有60种方法（可以算一下）。具体是哪60种方法，这个需要枚举一下。我们用num[i]表示第i种方案放置的炮兵数量。
比如：
PPPPHHPPPP
我们可以在第1个位置和第7个位置各放一个炮兵，这是一种可行的方案。此时num[i] = 2
假设一共有N行，
对于第s-2行，它有60种方案
对于第s-1行，它也有60种方案
对于第s行，它也有60种方案
对于第s+1行，它也有60种方案
.......
我们用dp[s][i][j]表示第s行使用第i种方案，第s-1行使用第j种方案时部队可以部署的最大值.那么max{dp[N][i][j], 其中i,j=1...60}的就是最后的答案
这里需要检验状态i和j是否互相兼容，这个可以通过连个状态的十进制表示的两个数间的&运算来判断（如果兼容，那么运算后的值必为0）
如果兼容，可以推出：
dp[s][i][j] = num[i] + max{dp[s-1][j][k], 其中k=1...60，并且i和k状态也时兼容的}
这表示：第s行使用第i种方案，第s-1行使用第j种方案时，我们枚举第s-2行的方案k。如果i,j,k这三种方案之间是相容的，那么dp[s][i][j] = num[i] + dp[s-1][j][k]
代码：
#include<stdio.h>
#include<string.h>
int cnt,m,n;
int dp[100][64][64],num[64],state[64],bitmap[100];
void init()
{
int tmp;
cnt=0;
for(int i=0;i<(1<<m);i++) //枚举每行的状态,从0到2^m - 1,判断其是否合法
{
tmp=i;
if( ((tmp<<1)&i) | ((tmp<<2)&i) ) continue;//判断该行在这个状态时是否合法（任意炮兵都不在其他炮兵的攻击范围之内）
state[cnt]=i; //通过数组state[]记录合法的状态（十进制表示）
num[cnt]=tmp&1; //num[]数组记录这个合法状态下‘1’的个数（也就时炮兵的个数）
while( tmp = (tmp>>1) )
num[cnt]+=tmp&1;
cnt++; //此函数的统计是假设当该行都为平地时，即共有cnt+1个合法状态
}
}
void solve()
{
int ans,i,j,k,p;
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++) //枚举每一行
for(j=0;j<cnt;j++) //先枚举第i行的可能状态
{
if(bitmap[i]&state[j]) continue; //地图中标记为“山地”的点不能布兵
if(i==0) dp[i][j][0]=num[j];
else if(i==1)
{
for(k=0;k<cnt;k++) //枚举第i-1行的可能状态
{
if(bitmap[i-1]&state[k]) continue; //判断第i-1行的k状态是否和山地冲突，冲突就跳到下一个状态k+1
if(state[j]&state[k]) continue; //判断上下两行(i-1和i)的合法状态是否兼容彼此
if(dp[i][j][k]<dp[i-1][k][0]+num[j])
dp[i][j][k]=dp[i-1][k][0]+num[j];
}
}
else
{
for(k=0;k<cnt;k++) //枚举第i-1行的可能状态
{
if(bitmap[i-1]&state[k]) continue; //判断第i-1行的k状态是否和山地冲突，冲突就跳到下一个状态k+1
if(state[j]&state[k]) continue; //判断上下两行(i-1和i)的合法状态是否兼容彼此
for(p=0;p<cnt;p++) //枚举第i-2行的可能状态
{
if(bitmap[i-2]&state[p]) continue; //判断第i-2行的p状态是否和山地冲突，冲突就跳到下一个状态p+1
if(state[k]&state[p] || state[j]&state[p]) continue;//判断上下两行(i-2和i-1,i-2和i)的合法状态是否兼容彼此
if(dp[i][j][k]<dp[i-1][k][p]+num[j])
dp[i][j][k]=dp[i-1][k][p]+num[j];
}
}
}
}
ans=0;
//for(i=0;i<n;i++)
for(j=0;j<cnt;j++)
for(k=0;k<cnt;k++)
if(dp[n-1][j][k]>ans)
ans=dp[n-1][j][k];
printf("%d\n",ans);
}
int main()
{
char s[12];
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(bitmap,0,sizeof(bitmap));
for(i=0;i<n;i++)
{
scanf("%s",s);
for(j=0;j<m;j++)if(s[j]=='H')bitmap[i]+=(1<<(m-1-j));
//if(s[j]=='H')bitmap[i]|=(1<<j);
}
init();
solve();
}
return 0;
}
/*算法回顾:
压缩状态的动态规划
1.利用二进制表示某个位置有无炮兵状态
2.把任意一行看成一个二进制串,并转化为相应的十进制数,即该行的压缩状态
3.枚举该行(i)所有二进制串,找出单独一行的所有可能的状态,即合法的压缩状态(s[i])
4.利用滚动数组降低内存消耗
技巧: 二进制的位运算,滚动数组
动规方程: f[i][j][k] = max{f[i-1][k][l]+c[j]},
f[i][j][k]表示第i行状态为s[j],第i-1行状态为s[k]的最大炮兵数
枚举l的每种状态,且s[j],s[k],s[l],地形互不冲突
*/