「NOI2001」炮兵阵地

题意：有一个 $n\times m$ 的地图，地图的每一格为山地(用 $H$ 表示)或平原(用 $P$ 表示)，在每一格平原地形上最多可布置一支炮兵部队(山地上不能部署)，一支炮兵部队在地图上的攻击范围如下图所示(蓝色区域为炮兵部署位置，红色区域为可攻击范围)：

P	H	$\color{red} P$	H	P
P	H	$\color{red} H$	P	H
$\color{red} P$	$\color{red} H$	$\color{blue} P$	$\color{red} H$	$\color{red} P$
H	H	$\color{red} P$	H	H
H	P	$\color{red} P$	H	H

即如果在某一个格部署一支部队，则沿横向左右各两格，纵向上下各两格都为其攻击范围。现在在不误伤的前提下(即任何一支部队不在其他部队的攻击范围内)，在整个地图最多能部署多少支部队？

又是状压 DP。。。

我们设 $f _{i,j,k}$ 代表当前行部署状态为 $j$，上一行部署状态为 $i$，当前转移到了第 $k$ 行的最大部署部队数。

设上上行的状态为 $l$，轻松得到状态转移方程为：

$$f_ {i,j,k}=\max(f _{i,j,k},f _{l,i,k-1}+sum _{j})$$

其中 $sum _{j}$ 代表 $j$ 状态中包含几个 $1$，即状态 $j$ 部署了几个部队。

但是题目的限制条件很恶心，我们来分析一下几个限制条件：

1. 部队必须部署在平原地形上

   我们把每一行的输入转为二进制数 $map _{i}$ (平原是 $0$，山地为 $1$)，判断当前状态 $j\ \text{and}\ map _{i}$ 结果是否为 $0$ 即可。若不为 $0$，则状态 $j$ 的一些部队部署在了山地上，不合法。

2. 部队之间左右距离大于 $2$ 格

   由于我们每一位存一个格子，那么我们把状态左移一格或两格再重新做按位与运算即可判断，即判断 $j\ \text{and}\ (j<<1)$ 和 $j\ \text{and}\ (j<<2)$ 是否为 $0$ 即可，不为 $0$ 则不合法。

3. 部队之间前后距离大于 $2$ 格

   同理，判断此行与上一行和上两行即可，即 $j\ \text{and}\ i$ 和 $j\ \text{and}\ l$ 是否为 $0$，不为 $0$ 则不合法。

最后由于只用到前两行，所以只用开一个 $3$ 行的滚动数组即可，同时第 $1$ 行的状态记得初始化。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=1<<12;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,m,sum[maxn],map[maxn],f[maxn][maxn][3];
char c;
int clac(int x)
{
	int num=0;
	while(x)
	{
		if(x&1)
			num++;
		x>>=1;
	}
	return num;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("\n");
		for(int j=1;j<=m;j++)
		{
			scanf("%c",&c);
			map[i]<<=1;
			if(c=='H')
				map[i]++;
		}
	}
	for(int i=0;i<(1<<m);i++)
		sum[i]=clac(i);
	for(int i=0;i<(1<<m);i++)
		if(!((i&map[1])||(i&(i<<1))||(i&(i<<2))))
			f[0][i][1]=sum[i];
	for(int i=0;i<(1<<m);i++)
		for(int j=0;j<(1<<m);j++)
			if(!((i&map[1])||(j&map[2])||(i&j)||(i&(i<<1))||(i&(i<<2))||(j&(j<<1))||(j&(j<<2))))
				f[i][j][2]=sum[i]+sum[j];
	for(int i=3;i<=n;i++)
		for(int j=0;j<(1<<m);j++)
		{
			if(j&map[i-1]||j&(j<<1)||j&(j<<2))
				continue;
			for(int k=0;k<(1<<m);k++)
			{
				if(k&j||k&(k<<1)||k&map[i]||k&(k<<2))
					continue;
				for(int l=0;l<(1<<m);l++)
				{
					if(l&j||l&map[i-2]||l&k||l&(l<<1)||l&(l<<2))
						continue;
					f[j][k][i%3]=max(f[j][k][i%3],f[l][j][(i-1)%3]+sum[k]);
				}
			}
		}
	int ans=-INF;
	for(int i=0;i<(1<<m);i++)
		for(int j=0;j<(1<<m);j++)
		{
			if(i&j||i&map[n-1]||j&map[n]||i&(i<<1)||i&(i<<2)||j&(j<<1)||j&(j<<2))
				continue;
			ans=max(ans,f[i][j][n%3]);
		}
	printf("%d",ans);
	return 0;
}