ProjectDP - 29
需要维护两行状态的状压DP
题目描述
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
description1
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入输出格式
输入格式
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。
输出格式
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
输入输出样例
输入样例
1
2
3
4
5
6
| 5 4
PHPP
PPHH
PPPP
PHPP
PHHP
|
输出样例
解题思路
看到这个玄学的数据范围，第一反应就是状压DP
我们设 表示当前正在摆放第 行，当前行的状态编号为 ，上一行的状态编号为 时的最大数量
我们先把所有的可能状态预处理出来，记为 stats[]
初始状态时所有的dp[1][i][1] = Popcount(stats[i])，其中 Popcount(x)表示x的二进制1的个数
转移方程显然，
Popcount(stats[j]) ，
其中 表示当前行的状态编号， 表示上一行的， 表示再上一行的
注意判一下地形是否符合，方法参见洛谷P1879
我要开滚动数组
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)
using std::cin;
using std::cout;
using std::endl;
const int MAXN = 100 + 10;
const int MAXM = 10 + 5;
const int MAX = (1 << 10) - 1 + 10;
int status[MAX], dp[2][MAX][MAX], can[MAXN];
int cnt, n, m;
char str[MAXM];
inline int pop(int x) {
int ret = 0;
while(x) {
if(x & 1) ret++;
x >>= 1;
}
return ret;
}
inline int Check(int a, int b) {
return a & b;
}
inline int Check3(int a, int b, int c) {
return Check(a,b) || Check(a,c) || Check(b,c);
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%s",str + 1);
for(int j = 1; j <= m; ++j)
if(str[j] == 'H')can[i] = (can[i] << 1) | 1;
else can[i] = can[i] << 1;
}
for(int i = 0; i <= (1 << m) - 1; ++i) {
if((!(i & (i << 2))) && (!(i & (i << 1))))
status[++cnt] = i;
}
for(int i = 1; i <= cnt; ++i)
dp[1 % 2][i][1] = pop(status[i]);
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= cnt; ++j) {
if (!(status[j] & can[i])) {
for (int k = 1; k <= cnt; ++k) {
if ((!(status[k] & can[i - 1])) && (!Check(status[j],status[k]))) {
for (int l = 1; l <= cnt; ++l){
if ((!(status[l] & can[i - 2])) && (!Check3(status[j], status[k], status[l])))
dp[i % 2][j][k] = std::max(dp[i % 2][j][k], dp[(i - 1) % 2][k][l] + pop(status[j]));
}
}
}
}
}
}
int ans = 0;
for(int i = 1; i <= cnt; ++i)
for(int j = 1; j <= cnt; ++j)
ans = std::max(ans, dp[n % 2][i][j]);
printf("%d\n", ans);
return 0;
}
|
description1