Description
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示）， 也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）； 一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。 图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内） ，在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input
第一行包含两个由空格分割开的正整数，分别表示N和M； 接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。 N≤100；M≤10。
Output
仅在第一行包含一个整数K，表示最多能摆放的炮兵部队的数量。
Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHPSample Output
6题目分析：
看到数据量 就会想到状压DP 首先要处理出每一行的每一个可行状态 储存一下
然后就开始dp
dp的状态：f[i][j][k],表示第i行选择第j种状态a，第i-1行选择第z种状态b时，最多布置的炮兵的个数。
dp[i][j][k]=max(dp[i][j][k],dp[i-1][z][j]+num[i][k]);
最后会发现MLE 因为状态转移只与三行有关 所以可以使用滚动数组
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
char s[200];
int getnum(int x)
{
int cnt=0;
while(x>0)
{
x=x&(x-1);
cnt++;
}
return cnt;
}
bool map[1100][1100];
int a[200][200];
int dp[200][200][200];
int num[200][200];
int ans;
void Dp()
{
a[0][0]=1;
int tmp=1;
for(int i=1;i<=n;i++,tmp=tmp^1)
for(int j=1;j<=a[i-1][0];j++)
for(int k=1;k<=a[i][0];k++)
if(map[a[i-1][j]][a[i][k]])
{
if(i==1)
dp[tmp][j][k]=max(dp[tmp][j][k],num[i][k]);
else
for(int z=1;z<=a[i-2][0];z++)
if(map[a[i-2][z]][a[i-1][j]]&&map[a[i-2][z]][a[i][k]])
dp[tmp][j][k]=max(dp[tmp][j][k],dp[tmp^1][z][j]+num[i][k]);
}
tmp=tmp^1;
for(int i=1;i<=a[n-1][0];i++)
for(int j=1;j<=a[n][0];j++)
ans=max(ans,dp[tmp][i][j]);
printf("%d",ans);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int q=0;
scanf("%s",&s[0]);
for(int j=0;j<m;j++)
if(s[j]=='P')q=q<<1;
else q=(q<<1)|1;
for(int j=0;j<(1<<m);j++)
{
if((j<<1)&j||(j<<2)&j||(j>>1)&j||(j>>2)&j||(q&j))
continue;
a[i][++a[i][0]]=j;
num[i][a[i][0]]=getnum(j);
}
}
for(int i=0;i<=(1<<m);i++)
for(int j=0;j<=(1<<m);j++)
if(!(i&j))map[i][j]=true;
Dp();
}