1. 为何状态压缩：
棋盘规模为n*m，且m≤10，如果用一个int表示一行上棋子的状态，足以表示m≤10所要求的范围。故想到用int s[num]。至于开多大的数组，可以自己用DFS搜索试试看；也可以遍历0~2^m-1，对每个数值的二进制表示进行检查；也可以用数学方法（？）
2. 如何构造状态：
当然，在此之前首先要想到用DP（？）。之后，才考虑去构造状态函数f(...)。
这里有一个链式的限制 ：某行上的某个棋子的攻击范围是2。即，第r行的状态s[i]，决定第r-1行只能取部分状态s[p]；同时，第r行的状态s[i]，第r-1行状态s[p]，共同决定第r-2行只能取更少的状态s[q]。当然，最后对上面得到的候选s[i], s[p], s[q]，还要用地形的限制去筛选一下即可。
简言之，第r行的威震第r-2行，因此在递推公式(左边=右边)中，必然同时出现r,和r-2两个行标；由于递推公式中行标是连续出现的，故在递推公式中必然同时出现r, r-1和r-2三个行标。由于在递推公式中左边包含一个f(...)，右边包含另一个f(...)，根据抽屉原理，r, r-1, r-2中至少有两个在同一个f(...)中，因此状态函数中必然至少包括相邻两行的行号作为两个维度。这就是为什么状态函数要涉及到两（相邻的）行，而不是一行。能想到的最简单形式如下：
dp[r][i][p]：第r行状态为s[i]，第r-1行状态为s[p]，此时从第0行~第r行棋子的最大数目为dp[r][i][p]
递推公式：
s[p]影响到s[q]的选取
----
| |
dp[r][i][p]=max{dp[r-1][p][q]}+sum[j], 其中sum[j]是状态s[j]中1的个数
| | |
---- |
s[i]影响到s[p]的选取 |
| |
----------------------------
代码如下：
#include <stdio.h>
#include <string.h>
#include <iostream>
#define MAX(a,b) (a)>(b)?(a):(b)
using namespace std;
int dp[][][]; //d[i][j][k]: “第i行状态是s[j]，第i-1行状态是s[k]”的
int s[]; //一行的状态选择s[0], s[1], ... , s[k-1]
int n,m; //n行×m列
int k; //一行的所有状态数
int map[]; //'H''P'地图map[0]~map[n-1]，地图每一行map[line]: 1001 表示HPPH
int sum[]; /*
很久就看推荐题目有这个了，一直没做，因为看了好几次没看懂，都说dp，这几天看了状态压缩后明白了，其实就是用
二进制来表示各个位置的状态然后进行枚举，把状态放进数组里就行，在这里用dp[i][j][k]表示第i行，当前j状态，
i-1行是k状态时候的最大炮数 dp[i][j][k]=MAX(dp[i][j][k],dp[i-1][k][p]+sum[j]) CAUTION:
1. 所有下标均从0开始
2. m<=10保证了可以用一个int存储一行的状态
*/ //状态s[x]是否造成行冲突
bool ok(int x)
{
if(x&(x<<))return false;
if(x&(x<<))return false;
return true;
} //状态s[x]下有多少个1
int getsum(int x)
{
int num=;
while(x>)
{
if(x&)num++;
x>>=;
}
return num;
} void find()
{
memset(s,,sizeof(s));
for(int i=;i<(<<m);i++) //i枚举所有m位的二进制数
{
if(ok(i))
{
s[k]=i;
sum[k++]=getsum(i);
} }
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
memset(dp,-,sizeof(dp)); int i;
for(i=;i<n;i++){
for(int j=;j<m;j++){
char tmp;
cin>>tmp;
if(tmp=='H')map[i]=map[i]|(<<j);//把第i行原始状态取反后放入map[i]
}
} k=;
find(); //1. 初始化第0行状态（只考虑有效状态，无效状态为-1）
for(i=;i<k;i++)
if(!(s[i]&map[])) //s[i]为1的位如果对应平原(0)，则&运算后为0
dp[][i][]=sum[i]; //2. 计算第1~n-1行状态（碰到无效状态,continue）
for(int r=;r<n;r++)
{
for(int i=;i<k;i++)//枚举第r行的状态 s[i]
{
if(map[r]&s[i]) continue; //通过地形排除部分第r行的状态 for(int p=;p<k;p++) //枚举第r-1行状态 s[p]
{
if(s[i] & s[p]) continue; //r与r-1没有想接触的 for(int q=;q<k;q++) //枚举第r-2行状态s[q]
{
if(s[p] & s[q]) continue; //Sam：这行是我加的
if(s[i] & s[q]) continue; //r与r-2行没有接触的 if(dp[r-][p][q]==-) continue; //所有不可能的情形dp[i][j][k]都为-1（初始化的值）
dp[r][i][p]=MAX(dp[r][i][p],dp[r-][p][q]+sum[i]);
}
}
}
} int ans=;
for(i=;i<k;i++)
for(int j=;j<k;j++)
ans=MAX(ans,dp[n-][i][j]);
printf("%d\n",ans);
} system("pause");
return ;
}