题解：P2704 [NOI2001] 炮兵阵地题解

# P2704 [NOI2001] 炮兵阵地 题解
## 题目概述
给定一个 `n` 乘 `m` 的矩阵，告诉你那些地方能放炮兵。但每个炮兵都有上下左右 2 格不能有其他的炮兵的限制。求最多能放多少的炮兵。
## 思路
根据题目所写的数据范围，一眼状压DP。

那先设个状态 $f[i][j][k]$ 表示在第 $i$ 行,状态为 $k$。第 $i-1$ 行,状态为 $j$。最多能放多少的炮兵。

那么来经典三步走。

### 1.赋初值

因为我们发现每个炮兵的限制都与本行，上面的 2 行，和下面的 2 行有关系。
但因为DP本质是类似于一种递推思想，故不考虑下面的两行，那么就要解决第一行和第二行的初值问题。

我们想第一行，只要它本行的炮兵不是相互冲突，那么就是一种合法情况了。

我们再来想第二行，因为第二行是建立在第一行的基础上的。故我们枚举两层循环分别表示一二行的情况，只要两层循环中的情况都是合法的，那么就可以更新第二层的情况。

### 2.列动态转移方程

因为自第三行起，每一行的情况都与前两行的情况有关。故我们枚举三层状态，只要每一行的状态都是合法的那么我们就可以进行，动态转移。

$f[i][j][k]=max(f[i][j][k],f[i-1]k1][j]+num[k]);//k为本行状态，j为上行状态，k1为上两行状态$

### 3.写出判断条件是否合法的函数

主要我们就是判断三种条件是否合法。分别是
- 在本行中当前枚举的状态与题目输入中给出的状态是否冲突

- 在本行以满足上一种条件的状态是否与本行左右相邻两个中不能有炮兵的条件冲突

- 在本行以满足上了两种情况的状态，是否与上两行中不能有相同位置的炮的情况冲突。

那么我们先来解决第一种，很容易想到的就是将所代表炮兵的 `P` 记为 1。代表不能放炮兵的山地`H`记为 0。那么我们每行都可以得到一个数，然后在与我们枚举的情况进行按位或。无论是我们枚举的情况，还是题目中给出的情况，只要这个地方为 1 也就是放了炮兵，那么在最后得到的数中这个 1 就会保留。我们只要对比最后得到的数中的 1 是否与题目输入中给出的 1 完全相同就可以了。

```cpp
	memset(q,1,sizeof(q));
	memset(f,0,sizeof(f));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			char c;
			cin>>c;
			if(c=='P') a[i][j]=1;
			else a[i][j]=0;
			q[i]=(q[i]<<1)+a[i][j];
		}
	m=pow(2,m)-1;
```
将题目所给的转换成数

**PS:若题目给的转换成数为0开头，我们就会上一位，故将代表数的 $p$ 数组赋初值为 1**

```cpp
for(int i=1; i<=n; i++)
		for(int j=1; j<=top; j++) {
			int g=p[j]|q[i];
			vis[i][j]=(g==q[i]);
		}
```

$vis[i][j]$ 表示第 `i` 行是否与第 `j` 种合法情况冲突。

接下来解决第二种情况，也就是本行内是否有冲突。我们想如果每一位为 1 那么它的改位的前两位和后两位都不能有 1。那既然如此我们就可以转换成左移一位和左移两位，以及右移一位与右移两位。判断与改位没有重叠的 1，可以用按位并且来处理。

```
bool checkh(int x) {
	int x1=x<<1;
	int x2=x<<2;
	if(((x1&x)|(x2&x))==0) {
		x1=x>>1;
		x2=x>>2;
		if(((x1&x)|(x2&x))==0) return 1;
		return 0;
	}
	return 0;
}
```

最后就是最简单的第三种情况了，在第三种情况中我们会得到三种状态，即为三个数我们只要判断这三个数中有没有重叠的 1 即可。我们可以想到用这三个数与，剩下的两个数进行按位与，如果没有重叠的 1 那么按位与的结果就会为 0。

```
bool checks(int x,int x1,int x2) {
	if(((x2&x1)|(x2&x)|(x1&x))==0) return 1;
	return 0;
}
```
# AC code:

```cpp
#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<string>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int N=3e2+5;
int n,m,top,ans,q[N],f[N][N][N],a[N][N],num[N],vis[N][N],p[N];
bool checkh(int x) {
	int x1=x<<1;
	int x2=x<<2;
	if(((x1&x)|(x2&x))==0) {
		x1=x>>1;
		x2=x>>2;
		if(((x1&x)|(x2&x))==0) return 1;
		return 0;
	}
	return 0;
}
bool checks(int x,int x1,int x2) {
	if(((x2&x1)|(x2&x)|(x1&x))==0) return 1;
	return 0;
}
int main() {
	scanf("%d%d",&n,&m);
	memset(q,1,sizeof(q));
	memset(f,0,sizeof(f));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			char c;
			cin>>c;
			if(c=='P') a[i][j]=1;
			else a[i][j]=0;
			q[i]=(q[i]<<1)+a[i][j];
		}
	m=pow(2,m)-1;
	for(int i=0; i<=m; i++)
		if(checkh(i)) {
			p[++top]=i;
			num[top]=__builtin_popcount(i);
		}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=top; j++) {
			int g=p[j]|q[i];
			vis[i][j]=(g==q[i]);
		}
	for(int i=1; i<=top; i++)
		if(vis[1][i]) f[1][0][i]=num[i];
	for(int i=1; i<=top; i++)
		if(vis[1][i])
			for(int j=1; j<=top; j++) {
				if(!vis[2][j]) continue;
				if(!checks(p[i],p[j],0)) continue;
				f[2][i][j]=max(f[2][i][j],f[1][0][i]+num[j]);
			}
	for(int i=3; i<=n; i++)
		for(int k3=1; k3<=top; k3++)
			if(vis[i][k3])
				for(int k2=1; k2<=top; k2++)
					if(vis[i-1][k2])
						for(int k1=1; k1<=top; k1++) {
							if(!vis[i-2][k1]) continue;
							if(checks(p[k1],p[k2],p[k3]))
								f[i][k2][k3]=max(f[i][k2][k3],f[i-1][k1][k2]+num[k3]);
						}
	if(n!=1)
		for(int j=1; j<=top; j++)
			for(int i=1; i<=top; i++) ans=max(ans,f[n][j][i]);
	if(n==1)
		for(int i=1; i<=top; i++) ans=max(ans,f[1][0][i]);
	printf("%d\n",ans);
	return 0;
}
```

**PS:在状压DP中我们会用到很多处理特殊状态的情况，但是要注意的是往往这些数组都是以，第几种合法状态的编号来存储。例如 $num[i]$ 表示在第 $i$ 种合法状态中 1 的个数。$i$ 表示的不是状态而是编号。**

正在渲染内容...

题解：P2704 [NOI2001] 炮兵阵地 题解

题解：P2704 [NOI2001] 炮兵阵地题解