题意：
司令部的将军们打算在 $N \times M$ 的网格地图上部署他们的炮兵部队。一个 $N \times M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
数据范围： $N \le 100,M \le 10$
题解：
算法：状压dp
由于一个炮兵可以影响到其之后两行的放置，所以考虑状压两行状态。使用 $dp[i][j][k]$ 表示第 $i$ 行的状态编号为 $j$ ，且上一行的状态编号为 $k$ 。易得状态转移方程：
$$dp[i][j][k]=max(dp[i-1][k][l]+sum[j])$$
其中 $l$ 为上上行的状态编号， $sum[j]$ 为状态编号为 $j$ 的状态中所含的炮兵个数。
在读入时，将地图信息状态压缩，每行用 $0/1$ 表示 $P/H$ ，代码如下：
for(int i=1;i<=n;i++){
scanf("%s",ch+1);
for(int j=1;j<=m;j++)
(f[i]<<=1)|=(ch[j]=='H');
}先预处理出前两行的dp信息，保证对地图信息合法，并同时计数所有单行合法状态 $stt[]$ ：
tot=(1<<m)-1;
for(int i=0;i<=tot;i++){
if(i&(i<<1) || i&(i<<2))
continue;
stt[++cnt]=i;
sum[cnt]=calc(i);
if(i&f[1])
continue;
dp[1][cnt][0]=sum[cnt];
}
for(int i=1;i<=cnt;i++){
int x=stt[i];
for(int j=1;j<=cnt;j++){
int y=stt[j];
if(f[2]&y || x&y)
continue;
dp[2][j][i]=dp[1][i][0]+sum[j];
}
}接下来进行dp：
for(int i=3;i<=n;i++)
for(int j=1;j<=cnt;j++){
int x=stt[j];
if(f[i]&x)
continue;
for(int k=1;k<=cnt;k++){
int y=stt[k];
if(x&y)
continue;
for(int l=1;l<=cnt;l++){
int z=stt[l];
if(x&z || y&z)
continue;
dp[i][j][k]=Max(dp[i][j][k],dp[i-1][k][l]+sum[j]);
}
}
}因为当前行状态仅依赖于前两行，所以考虑滚动数组优化：
for(int i=3;i<=n;i++)
for(int j=1;j<=cnt;j++){
int x=stt[j];
if(f[i]&x)
continue;
for(int k=1;k<=cnt;k++){
int y=stt[k];
if(x&y)
continue;
for(int l=1;l<=cnt;l++){
int z=stt[l];
if(x&z || y&z)
continue;
dp[i%3][j][k]=Max(dp[i%3][j][k],dp[(i-1)%3][k][l]+sum[j]);
}
}
}最后统计答案即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
const int M=10;
int n,m;
int tot,cnt,ans;
char ch[M];
int f[N],stt[1<<M],sum[1<<M],dp[3][1<<M][1<<M];
template <typename T>
inline T Max(T a,T b){
return a>b?a:b;
}
inline int calc(int x){
int res=0;
for(;x;x&=x-1)
res++;
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",ch+1);
for(int j=1;j<=m;j++)
(f[i]<<=1)|=(ch[j]=='H');
}
tot=(1<<m)-1;
for(int i=0;i<=tot;i++){
if(i&(i<<1) || i&(i<<2))
continue;
stt[++cnt]=i;
sum[cnt]=calc(i);
if(i&f[1])
continue;
dp[1][cnt][0]=sum[cnt];
}
for(int i=1;i<=cnt;i++){
int x=stt[i];
for(int j=1;j<=cnt;j++){
int y=stt[j];
if(f[2]&y || x&y)
continue;
dp[2][j][i]=dp[1][i][0]+sum[j];
}
}
for(int i=3;i<=n;i++)
for(int j=1;j<=cnt;j++){
int x=stt[j];
if(f[i]&x)
continue;
for(int k=1;k<=cnt;k++){
int y=stt[k];
if(x&y)
continue;
for(int l=1;l<=cnt;l++){
int z=stt[l];
if(x&z || y&z)
continue;
dp[i%3][j][k]=Max(dp[i%3][j][k],dp[(i-1)%3][k][l]+sum[j]);
}
}
}
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
ans=Max(ans,dp[n%3][i][j]);
printf("%d",ans);
return 0;
}