[文章目录]
Description
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示）， 也可能是平原（用“P”表示）。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；
如果在地图中的平原上部署一支炮兵部队，则它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内） ，在整个地图区域内最多能够摆放多少我军的炮兵部队。n < =200,m < =10
显然是状压DP，把每行状态压成一个二进制数，然后预处理每一行不互相伤害的状态，发现m==10时总共只有60种合法状态。由此进行DP。
先说一下判断，一开始写的是暴力
然而可以运用神奇的位运算，左右移再或一下就好了。不过不要忘了可以炸间距一个格的炮兵。
然后再谈DP
第一种WA法：
将每一行的状态变成一个结构体，记录所有的可行状态，再加上当前位置的num。缺点：会有重复状态，到了后面种类会变得很多60^n，沃日！！！
第二种WA法：
f[x][y]表示第x行选y状态的最大炮兵数。
所以f[x][k]=max(f[x][k],num[j]+f[z][i]+num[k]);其中j状态与k，i，不重合，并且k状态为x行的一个状态的子集，由此进行DP（第1，2行比较棘手）。忽略了上一行和上上一行的状态最优解对应其他行的状态是否是同一个状态的问题。
第3种AC法：
f[i][j][k]表示第i行状态是第j个，而它上一行状态是第k个的最大的布置炮兵数。一边过233（hhh）
AC代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int ans,col[200],n,m;
int dp[100],tot,num[100];
int f[110][110][110];
char ch;
int work(int x)
{
int re=0;
while(x)
{
if(x&1) re++;
x>>=1;
}
return re;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
{
ch=getchar();
while(ch!='H'&&ch!='P') ch=getchar();
if(ch=='P')
col[i]+=(1<<j);
}
for(int s=0;s<(1<<m);s++)
if((s&(s<<2))==0&&(s&(s>>2))==0&&(s&(s>>1))==0&&(s&(s<<1))==0)
dp[++tot]=s, num[tot]=work(s);
for(int i=1;i<=n;i++)
for(int j=1;j<=tot;j++)
{
if((col[i]|dp[j])!=col[i]) continue;
for(int k=1;k<=tot;k++)
{
if((dp[j]&dp[k])!=0) continue;
for(int s=1;s<=tot;s++)
{
if((dp[s]&dp[j])!=0) continue;
f[i][j][k]=max(f[i][j][k],f[i-1][k][s]+num[j]);
}
}
}
for(int i=1;i<=tot;i++)
for(int j=1;j<=tot;j++)
ans=max(f[n][i][j],ans);
printf("%d",ans);
return 0;
}