印象中这道题好像我曾经肝过，但是没肝出来，现在肝出来了也挺开心的![POJ 1185 - 炮兵阵地 & HDU 4539 - 郑厂长系列故事——排兵布阵 - [状压DP]](https://image.shishitao.com:8440/aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhCekwybHRZV2RsY3pJd01UY3VZMjVpYkc5bmN5NWpiMjB2WW14dlp5OHhNVEF6TVRrNEx6SXdNVGN3T1M4eE1UQXpNVGs0TFRJd01UY3dPVEkzTWpJME56RXhOalV6TFRrNE5qUTBNVEV3Tmk1d2JtYz0uanBn.jpg?w=700&webp=1 "POJ 1185 - 炮兵阵地 & HDU 4539 - 郑厂长系列故事——排兵布阵 - [状压DP]")
题目链接：http://poj.org/problem?id=1185
Time Limit: 2000MS Memory Limit: 65536K
Description
![POJ 1185 - 炮兵阵地 & HDU 4539 - 郑厂长系列故事——排兵布阵 - [状压DP]](https://image.shishitao.com:8440/aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhBdmNHOXFMbTl5Wnk5cGJXRm5aWE12TVRFNE5WOHhMbXB3Wnc9PS5qcGc%3D.jpg?w=700&webp=1 "POJ 1185 - 炮兵阵地 & HDU 4539 - 郑厂长系列故事——排兵布阵 - [状压DP]")
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。
Output
Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output
6
题解：
感谢博文http://www.cnblogs.com/scau20110726/archive/2013/02/27/2935256.html，可以说讲的非常清晰了；
首先，一个炮的攻击范围有两格，所以对于第i行来讲，i-1行和i-2行对它有影响，i-3行及以上的都没有影响了；
所以我们要去求得到关于第i行的一些信息，只需要知道i-1和i-2的信息即可；
然后考虑表示地图：
山用1表示，空地用0表示；那么对于一行，就是一个0 or 1的串，这是个二进制数，可以状压成一个十进制数；
再考虑表示一行上部署炮兵部队的状态：
只考虑一行上，能不能放炮的话，状态最大达到 (1<<10) - 1 = 2^10 -1；
但是实际上，因为炮与炮之间不能相互攻击的限制，状态数没有那么多；
假设一个状态i，如果满足 (i&(i<<1)) == 0 && (i&(i<<2)) == 0 的话，它才是一个符合炮与炮之间相互不能攻击的状态；
由此，我们通过枚举计算一下到底有多少状态：
for(int i=;i<=(<<10)-;i++) if( (i&(i<<))== && (i&(i<<))== ) cnt++;
程序运行得到的cnt等于60，所以我们可以知道，最大的状态数不会超过60；
由此使用一个state[]数组保存状态（依然状压成十进制数），把每次枚举出来可行的状态保存进去；
并且值得一提的是，我们把state定义成结构体数组：
state[i].sta：表示第i个状态时怎么样的；
state[i].cnt：记录这个状态下，部署了多少炮兵部队；
这样一来，方便后续操作，也不容易出错，在枚举求得所有可行状态时，也可以一并求出cnt；
那么怎么判断炮兵部队不在山上呢？ 只要state[i] & mp[r] == 0 ,就表示state[i]这个状态，可以放在r这行上，而且炮不会在山上，炮之间也不会攻击；
那么又如何判断 i行，i-1行，i-2行的炮没有冲突呢？所以我们假设现在i行，i-1行，i-2行的炮的摆放情况分别是state[i],state[j],state[k]；
当满足 state[i] & state[j] == 0 state[i] & state[k] == 0 state[j] & state[k] == 0 条件时，三行的部署情况没有冲突；
最后的状态转移方程，可以直接参考代码中的状态转移过程；
AC代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 103
#define MAXM 11
using namespace std;
int n,m;
int mp[MAXN]; int state_num;
struct State{
int sta,cnt;
}state[]; int dp[MAXN][][]; int main()
{
scanf("%d%d",&n,&m); for(int i=;i<=n;i++)
{
mp[i]=;
char input[];
scanf("%s",input+);
for(int j=;j<=m;j++)
{
int tmp=((input[j]=='H')?:);
mp[i]|=tmp;
if(j!=m) mp[i]=mp[i]<<;
}
}//二进制记录地图 state_num=;
for(int i=;i<=(<<m)-;i++)
{
if( (i&(i<<))== && (i&(i<<))== )
{
state_num++;
state[state_num].sta=i; state[state_num].cnt=;
for(int tmp=i;tmp;tmp=(tmp>>)) if(tmp&) state[state_num].cnt++; //printf("id=%d state=%d cnt=%d\n",state_num,state[state_num].sta,state[state_num].cnt);
}
}//单纯在炮与炮之间不能互相攻击的限制下，得到所有状态 //状态转移过程 - st
memset(dp,,sizeof(dp)); for(int i=;i<=state_num;i++)
{
if(state[i].sta & mp[]) continue;
dp[][i][]=state[i].cnt;
}//初始化dp[1][ state of row1 ][ no state ] for(int i=;i<=state_num;i++)//枚举第2行状态
{
if(state[i].sta & mp[]) continue;
for(int j=;j<=state_num;j++)//枚举第1行状态
{
if( (state[j].sta&mp[]) || (state[i].sta&state[j].sta) ) continue;
dp[][i][j]=max(dp[][i][j],dp[][j][]+state[i].cnt);
}
}//初始化dp[2][ state of row2 ][ state of row1 ] for(int r=;r<=n;r++)
{ for(int i=;i<=state_num;i++)//枚举第r行状态
{ if(state[i].sta & mp[r]) continue; for(int j=;j<=state_num;j++)//枚举第r-1行状态
{ if( (state[j].sta&mp[r-]) || (state[i].sta&state[j].sta) ) continue; for(int k=;k<=state_num;k++)//枚举第r-2行状态
{
if(state[k].sta & mp[r-]) continue;
if( (state[i].sta&state[k].sta) || (state[j].sta&state[k].sta) ) continue; dp[r][i][j]=max(dp[r][i][j],dp[r-][j][k]+state[i].cnt);
} } } }
//状态转移过程 - ed int ans=;
for(int i=;i<=state_num;i++)
{
for(int j=;j<=state_num;j++)
{
ans=max(ans,dp[n][i][j]);
}
}
printf("%d\n",ans);
}
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4539
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
也不是副厂长
他根本就不是厂长
事实上
他是带兵打仗的团长
一天，郑厂长带着他的军队来到了一个n*m的平原准备布阵。
根据以往的战斗经验，每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然，一个士兵不能站在另外一个士兵所能攻击到的位置，同时因为地形的原因平原上也不是每一个位置都可以安排士兵。
现在，已知n,m
以及平原阵地的具体地形，请你帮助郑厂长计算该阵地,最多能安排多少个士兵。
每组数据的第一行包含2个整数n和m (n <= 100, m <=
10 )，之间用空格隔开；
接下来的n行，每行m个数，表示n*m的矩形阵地，其中1表示该位置可以安排士兵，0表示该地形不允许安排士兵。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 103
#define MAXM 11
using namespace std;
int n,m;
int mp[MAXN]; int state_num;
struct State{
int sta,cnt;
}state[]; int dp[MAXN][][]; int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=,tmp;i<=n;i++)
{
mp[i]=;
for(int j=;j<=m;j++)
{
scanf("%d",&tmp);
tmp=!tmp;
mp[i]|=tmp;
if(j!=m) mp[i]=mp[i]<<;
}
}//二进制记录地图 state_num=;
for(int i=;i<=(<<m)-;i++)
{
if( (i&(i<<))== )
{
state[state_num].sta=i; state[state_num].cnt=;
for(int tmp=i;tmp;tmp=(tmp>>)) if(tmp&) state[state_num].cnt++; //printf("id=%d state=%d cnt=%d\n",state_num,state[state_num].sta,state[state_num].cnt);
state_num++;
}
}//单纯在士兵与士兵之间不能互相攻击的限制下，得到所有状态 //状态转移过程 - st
memset(dp,,sizeof(dp)); for(int i=;i<state_num;i++)
{
if(state[i].sta & mp[]) continue;
dp[][i][]=state[i].cnt;
}//初始化dp[1][ state of row1 ][ no state ] for(int i=;i<state_num;i++)//枚举第2行状态
{
if(state[i].sta & mp[]) continue;
for(int j=;j<state_num;j++)//枚举第1行状态
{
if(state[j].sta & mp[]) continue;
if((state[j].sta<<)&state[i].sta || (state[j].sta>>)&state[i].sta) continue;
dp[][i][j]=max(dp[][i][j],dp[][j][]+state[i].cnt);
}
}//初始化dp[2][ state of row2 ][ state of row1 ] for(int r=;r<=n;r++)
{ for(int i=;i<state_num;i++)//枚举第r行状态
{ if(state[i].sta & mp[r]) continue; for(int j=;j<state_num;j++)//枚举第r-1行状态
{ if(state[j].sta & mp[r-]) continue;
if((state[j].sta<<)&state[i].sta || (state[j].sta>>)&state[i].sta) continue;
for(int k=;k<state_num;k++)//枚举第r-2行状态
{
if(state[k].sta & mp[r-]) continue;
if(state[i].sta & state[k].sta) continue;
if((state[k].sta<<)&state[j].sta || (state[k].sta>>)&state[j].sta) continue; dp[r][i][j]=max(dp[r][i][j],dp[r-][j][k]+state[i].cnt);
} } } }
//状态转移过程 - ed int ans=;
for(int i=;i<state_num;i++)
{
for(int j=;j<state_num;j++)
{
ans=max(ans,dp[n][i][j]);
}
}
printf("%d\n",ans);
}
}