司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上能攻击到上下左右两个格
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
这道题一看(M)那么小，每个点只有两种状态，那就肯定是状压(dp)了，至于什么是状压(dp)，简单来说就是将连续的一串数据转化成一个数的形式来存，这道题就可以将每一行都转化为一个二进制数，用(1)表示选，用(0)表示不选。但是因为还有平原和山地这样的限制条件，我们就可以将这个条件存下来，用(1)表示平原，即为可以放；用(0)表示山地，即为不可以放。然后我们对每种放的状态预处理出来，写出转移方程就可以(dp)了。（很多状压(dp)题都可以这么做）
刚开始我做的时候是用(f[i][j])表示第(i)行的排列方式为(j)时，前(i)行的最大炮兵数，写出状态转移方程：(f[i][j]=max(f[i-1][k])+num[j])，其中(k)为第(i-1)行的合法的一种排列，(num[j])表示一行中第(j)种排列的炮兵数，然后枚举(i-1)行的状态，即为(k)；(i-2)行的状态。这样做显然是不行的，因为有的不合法的情况用来更新答案了。(也就我这样的zz会想出这么sb的做法）
所以我们考虑加一维，来维护第(i-1)行的状态，那么(f[i][j][k])表示第(i)行的排列方式为(j)时，且第(i-1)行的排列方式为(k)时，前(i)行的最大炮兵数，方程也很好写:(f[i][j][k]=max(f[i-1][k][h])+num[j])，其中(h)为第(i-2)行的合法的一种排列，初始化：(f[1][i][0]=num[i])（(i)的这种排列合法），(dp)时注意下在第(2)行时用(f[i-1][k][0])比较就行了，然后这道题做完了。
Code
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,goal[500],zh[200],f[200][500][500],state[5000],cnt,num[5000],ans;
void make()
{
for (int i=0;i<(1<<m);i++)
if (!(i&(i<<1))&&!(i&(i<<2))) //如果这个格子放炮兵，那么四周不能放，四周再往外一格也不能放，所以将i按位与i左移1位和左移两位
{
state[++cnt]=i;
int x=i;
while (x)
{
num[cnt]+=x%2; //统计这种排列方案的炮兵数
x>>=1;
}
}
}
int main()
{
cin>>n>>m;
char x;
zh['P']=1;
zh['H']=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
cin>>x;
goal[i]=goal[i]*2+zh[x]; //把题目中的限制表示的二进制转换为十进制
}
make(); //预处理出这一行可行的排列
for (int i=1;i<=cnt;i++)
if ((state[i]|goal[1])==goal[1])
f[1][i][0]=num[i]; //初始化
for (int i=2;i<=n;i++)
for (int j=1;j<=cnt;j++)
for (int k=1;k<=cnt;k++)
for (int h=1;h<=cnt;h++)
{
if (state[j]&state[k])continue;
if (state[k]&state[h])continue;
if (state[h]&state[j])continue;
//前三个均为上下不相邻
if ((state[j]|goal[i])!=goal[i])continue;
if ((state[k]|goal[i-1])!=goal[i-1])continue;
if ((state[h]|goal[i-2])!=goal[i-2])continue;
//后三个为符合放置在平地上
if (i==2)f[i][j][k]=max(f[i][j][k],f[i-1][k][0]+num[j]); //第二行时用来更新状态的第一行的f没有上一行，所以特别处理一下
f[i][j][k]=max(f[i][j][k],f[i-1][k][h]+num[j]);
}
for (int i=1;i<=cnt;i++)
for (int j=1;j<=cnt;j++)
ans=max(ans,f[n][i][j]); //在最后一行和倒数第二行的所有排列中取个最大值
cout<<ans<<endl;
return 0;
}