[NOI2001] 炮兵阵地

题意

给定一个 n x m 的地图，P 是平原，H 是山地。

只能在平原上放炮兵，每个格子最多放一支。

炮兵会攻击：

同一行左右距离 1 或 2 的格子
同一列上下距离 1 或 2 的格子

要求在互不攻击的前提下，求最多能放多少支炮兵。

思路

先看一个适合小数据理解和对拍的暴力：

cpp

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#include <bits/stdc++.h>
using namespace std;

int n, m;
string g[15];
int board[15][15];
int ans;

bool ok_place(int x, int y) {
    if (g[x][y] == 'H') {
        return false;
    }
    // 炮兵会攻击同一行或同一列上距离 1 或 2 的格子。
    int dx[8] = {0, 0, 0, 0, 1, -1, 2, -2};
    int dy[8] = {1, -1, 2, -2, 0, 0, 0, 0};
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (1 <= nx && nx <= n && 1 <= ny && ny <= m && board[nx][ny]) {
            return false;
        }
    }
    return true;
}

void dfs_cell(int pos, int used) {
    if (pos == n * m) {
        ans = max(ans, used);
        return;
    }

    int x = pos / m + 1;
    int y = pos % m + 1;

    dfs_cell(pos + 1, used);
    if (ok_place(x, y)) {
        board[x][y] = 1;
        dfs_cell(pos + 1, used + 1);
        board[x][y] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据逐格枚举是否放炮兵。
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> g[i];
        g[i] = " " + g[i];
    }
    memset(board, 0, sizeof(board));
    ans = 0;
    dfs_cell(0, 0);
    cout << ans << '\n';
    return 0;
}

暴力会逐格枚举放还是不放，复杂度接近 2^(n*m)，只能做很小的数据。

正解的关键是观察攻击范围：

同一行里，只会影响左右两格以内
纵向上，只会影响上下两行的同一列

所以当我们按行处理时，当前行是否合法，只和：

当前行自己
上一行
上上行

这三行有关。

于是可以把每一行压成一个二进制状态。

先预处理出所有单行合法状态 s，要求同一行中不能出现距离 1 或 2 的两个炮兵。

然后设 DP 状态表示最近两行的摆法，转移时枚举当前行状态 cur，检查：

cur 不能放到山地上
cur 不能和上一行 pre1 同列冲突
cur 不能和上上行 pre2 同列冲突

满足条件就可以转移。

DP 转移方程

设当前行状态为 cur，上一行为 pre1，上上行为 pre2，则：

dp[i][pre1][cur] = \max(dp[i][pre1][cur],\ dp[i-1][pre2][pre1]+popcount(cur))

前提是 cur 不压到山地，且 cur 与 pre1/pre2 都没有同列冲突。

这样就把整张图的搜索，压成了“枚举每一行合法状态”的状压 DP。

代码

cpp

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
89
90
91
92
93
94
95
96
97
98
99
100#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXS = 1 << 10;

int n, m;
int row_mask[MAXN];          // row_mask[i] 的 1 表示这一列是山地，不能放炮兵
int states[MAXS], state_cnt; // 所有单行合法状态
int bit_cnt[MAXS];           // bit_cnt[s] 表示状态 s 里放了多少个炮兵
int dp[2][MAXS][MAXS];
// dp[cur][s1][s2]：
// 已经处理到当前这一行时，当前行状态是 s1，上一行状态是 s2 的最大炮兵数。

bool ok_self(int s) {
    // 同一行里，距离 1 或 2 的两个炮兵都会互相攻击。
    if (s & (s << 1)) {
        return false;
    }
    if (s & (s << 2)) {
        return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        int mask = 0;
        for (int j = 0; j < m; j++) {
            if (s[j] == 'H') {
                mask |= 1 << j;
            }
        }
        row_mask[i] = mask;
    }

    int full = 1 << m;
    state_cnt = 0;
    for (int s = 0; s < full; s++) {
        if (ok_self(s)) {
            states[state_cnt++] = s;
            bit_cnt[s] = __builtin_popcount((unsigned int) s);
        }
    }

    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;

    for (int row = 1; row <= n; row++) {
        int now = row & 1;
        int pre = now ^ 1;
        memset(dp[now], -1, sizeof(dp[now]));

        for (int i = 0; i < state_cnt; i++) {
            int cur = states[i];
            // 当前行不能把炮兵放在山地上。
            if (cur & row_mask[row]) {
                continue;
            }
            for (int j = 0; j < state_cnt; j++) {
                int pre1 = states[j];
                // 与上一行同列时会互相攻击。
                if (cur & pre1) {
                    continue;
                }
                for (int k = 0; k < state_cnt; k++) {
                    int pre2 = states[k];
                    // 与上上行同列时也会互相攻击。
                    if (cur & pre2) {
                        continue;
                    }
                    if (dp[pre][pre1][pre2] == -1) {
                        continue;
                    }
                    // 行号整体向下推进一格：
                    // 原来的上一行变成上上行，当前行变成新的上一行。
                    dp[now][cur][pre1] = max(dp[now][cur][pre1],
                                             dp[pre][pre1][pre2] + bit_cnt[cur]);
                }
            }
        }
    }

    int last = n & 1;
    int ans = 0;
    for (int i = 0; i < state_cnt; i++) {
        for (int j = 0; j < state_cnt; j++) {
            ans = max(ans, dp[last][states[i]][states[j]]);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

设单行合法状态个数为 S，则时间复杂度为 $O(n * S^3)$ ，空间复杂度为 $O(S^2)$ 。

总结

这题的核心不是“网格”，而是“攻击范围只影响最近两行”。

一旦抓住这个局部性，就可以自然地想到按行状压，并只保留前两行状态。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 转移方程

代码

复杂度

总结

一图流解析