NOI2001 炮兵阵地（状压dp）

题目描述

司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑***域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入格式

第一行包含两个由空格分割开的正整数，分别表示N和M；

接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。

输出格式

仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

输入输出样例

输入 #1

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出 #1

6

分析

这道题明显是状压dp（面向数据范围编程）。我们要记录的是第 $i$i 行和第 $i-1$i−1 行的状态。
因为这一行的状态是由前两行的状态决定的（一个炮能打两行）。
于是我们记
$cnt\left[s\right]$cnt[s] 表示状态 $s$s 中有的 $1$1 的数量。
$f\left[i\right]\left[s1\right]\left[s2\right]$f[i][s1][s2]表示第 $i$i 行状态为 $s1$s1, $i-1$i−1 行状态为 $s2$s2 的最大炮车数量。
可以得到转移方程：
$f\left[i\right]\left[s1\right]\left[s2\right]=max\left(f\right[i\left]\right[s1\left]\right[s2],f[i-1\left]\right[s2\left]\right[s3]+cnt[s1\left]\right)$f[i][s1][s2]=max(f[i][s1][s2],f[i−1][s2][s3]+cnt[s1])
而我们发现空间复杂度高达 $100\ast 2^{10}\ast 2^{10}=10^8$100∗210∗210=108，显然存不下嘛，时间复杂度的话，因为要枚举三行的状态，复杂度更加爆炸。
怎么优化呢？不难发现，很难发现，每一行合法的状态是有限的，最多有60个，这一点我们可以通过以下代码来实现：

for(i = 0; i < (1 << 10); i++){
	if(!(i & (i >> 1)) && !(i & (i >> 2))) cnt++;
} 

得到的 $cnt$cnt 就是 $60$60 了。
于是时空复杂度都降低了很多很多。

下面是代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int sta[65], ret, cnt[65], a[105];
LL f[105][65][65], ans;
char s[15];
int w(int x){
	int s = 0;
	while(x){
		s++;
		x -= x&-x;
	}
	return s;
}
int main(){
	int i, j, t, k, n, m;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++){
		scanf("%s", s);
		for(j = 0; j < m; j++){
			if(s[j] == 'H') a[i] |= (1 << j);
		}
	}
	for(i = 0; i < (1 << m); i++){
		if(!(i & (i >> 1)) && !(i & (i >> 2))){
			sta[++ret] = i;
			cnt[ret] = w(i);
		}
	}
	for(i = 1; i <= ret; i++){
		if(!(sta[i] & a[1])) f[1][i][1] = cnt[i];
	}
	for(i = 2; i <= n; i++){
		for(j = 1; j <= ret; j++){
			if(!(a[i-2] & sta[j])){
				for(k = 1; k <= ret; k++){
					if(!(a[i-1] & sta[k]) && !(sta[k] & sta[j])){
						for(t = 1; t <= ret; t++){
							if(!(a[i] & sta[t]) && !(sta[k] & sta[t]) && !(sta[j] & sta[t])){
								f[i][t][k] = max(f[i][t][k], f[i-1][k][j] + cnt[t]);
							}
							if(i == n) ans = max(ans, f[i][t][k]);
						}
					}
				}
			}
		}
	}
	printf("%lld", ans);
	return 0;
}