POJ-1185 炮兵阵地

Posted on | In

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

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

题目链接

Input
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符(‘P’或者’H’)，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。

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

Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output
6

状压DP模版题

由于每行长度不超过10，可以考虑将每行的状态进行压缩。对于原地图，将山地对应二进制位置为1，平原对应置为0。摆放方案中部署炮兵的位置置为1，否则置为0。

因为同一行的炮兵间距离至少为2，故每行状态数不超过70。可先将状态及其对应炮兵数预处理出来，然后枚举可行状态即可。

转移方程： $ dp[i][j][k] = \max(dp[i][j][k], dp[i - 1][k][t] + num[j])$

所求结果为： $res = \max(dp[n][j][k])$

其中i为行数，j为当前行状态，k为i-1行状态，t为i-2行状态。

Code:

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
85
86
87
88
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

// status->状态，num->炮兵数， tot->总状态数
int status[70], num[70], tot;

int dp[105][70][70];

// 预处理可行状态
void init(int mx) {
    tot = 0;
    for (int i = 0; i < mx; i++) {
        if ((i & (i << 1)) || (i & (i >> 1))) continue;
        if ((i & (i << 2)) || (i & (i >> 2))) continue;
        status[tot++] = i;
    }
    for (int j = 0; j < tot; j++) {
        int i = status[j];
        for (num[j] = 0; i; i >>= 1) {
            if (i & 1) {
                num[j]++;
            }
        }
    }
}

// a->地图状态
int n, m, a[105];
char s[12];

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        init(1 << m);

        // 地图状态
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            a[i] = 0;
            for (int j = 0; j < m; j++) {
                if (s[j] == 'H') {
                    a[i] |= 1 << j;
                }
            }
        }
        memset(dp, 0, sizeof dp);

        // 第一行
        for (int i = 0; i < tot; i++) {
            if (a[0] & status[i]) continue;
            dp[0][i][0] = num[i];
        }

        // 第二行
        for (int i = 0; i < tot; i++) {
            if (a[1] & status[i]) continue;
            for (int j = 0; j < tot; j++) {
                if (status[i] & status[j]) continue;
                dp[1][i][j] = max(dp[1][i][j], dp[0][j][0] + num[i]);
            }
        }

        // 第三行及以后
        for (int i = 2; i < n; i++) {
            for (int j = 0; j < tot; j++) {
                if (a[i] & status[j]) continue;
                for (int k = 0; k < tot; k++) {
                    if ((a[i - 1] & status[k]) || (status[j] & status[k])) continue;
                    for (int t = 0; t < tot; t++) {
                        if (a[i - 2] & status[t] || (status[j] & status[t]) || (status[k] & status[t])) {
                            continue;
                        }
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][t] + num[j]);
                    }
                }
            }
        }

        int res = 0;
        for (int i = 0; i < tot; i++) {
            for (int j = 0; j < tot; j++) {
                res = max(res, dp[n - 1][i][j]);
            }
        }
        printf("%d\n", res);
    }
}