[GDOI2014] 拯救莫莉斯

题意

在网格图上选择一些格子建油库，使得每个格子都被自己或四邻中的油库覆盖。

要求先最小化总代价；若总代价相同，再最小化油库数量。

思路

先看一个小数据暴力：

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

long long w[10][10];
int n, m;
long long best_cost;
int best_cnt;

bool better(long long cost, int cnt) {
    if (cost != best_cost) {
        return cost < best_cost;
    }
    return cnt < best_cnt;
}

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

    // brute.cpp：直接枚举哪些格子建油库，检查是否覆盖整张图。
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> w[i][j];
        }
    }

    int tot = n * m;
    best_cost = (1LL << 60);
    best_cnt = tot + 1;

    for (int mask = 0; mask < (1 << tot); mask++) {
        vector<vector<int> > cover(n, vector<int>(m, 0));
        long long cost = 0;
        int cnt = 0;
        for (int id = 0; id < tot; id++) {
            if (!(mask & (1 << id))) {
                continue;
            }
            int x = id / m;
            int y = id % m;
            cost += w[x][y];
            cnt++;
            int dx[5] = {0, 1, -1, 0, 0};
            int dy[5] = {0, 0, 0, 1, -1};
            for (int k = 0; k < 5; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    cover[nx][ny] = 1;
                }
            }
        }
        bool ok = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!cover[i][j]) {
                    ok = false;
                }
            }
        }
        if (ok && better(cost, cnt)) {
            best_cost = cost;
            best_cnt = cnt;
        }
    }

    cout << best_cnt << ' ' << best_cost << '\n';
    return 0;
}

暴力会枚举每个格子建不建油库，再检查是否覆盖整张图。

正解利用“一个格子是否被覆盖，只和上下左右有关”这一点，做按行推进的轮廓 DP。

把较短的一维作为状态宽度，转成 W <= 7。

然后设每一行的建库方案是一个二进制状态。

当我们处理到三行 up, mid, down 时，中间这一行是否已被完全覆盖就可以被完全确定：

mid 自己建库
up / down 负责上下覆盖
mid 左右移位负责左右覆盖

所以可以写一个 row_ok(up, mid, down) 检查函数。

DP 时维护相邻两行状态，不断枚举下一行状态并转移。

DP 转移方程

设状态保留最近两行 (pre, cur)，枚举下一行 nxt。若 row_ok(pre, cur, nxt) 成立，就可以转移：

dp[cur][nxt] = \min(dp[cur][nxt],\ dp[pre][cur] + cost(nxt))

这里的 min 是双关键字比较：先比较总代价，再比较油库数量。

由于题目有双关键字，需要把每个状态的值记成：

总花费
油库数量

比较时先比花费，再比数量。

代码

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 60);
const int MAXW = 8;
const int MAXS = 1 << 7;

struct State {
    long long cost;
    int cnt;
};

int n, m;
long long a[55][55];
long long cost_sum[55][MAXS];
State dp[2][MAXS][MAXS];

bool better(const State &x, const State &y) {
    if (x.cost != y.cost) {
        return x.cost < y.cost;
    }
    return x.cnt < y.cnt;
}

State add_state(const State &x, long long add_cost, int add_cnt) {
    if (x.cost >= INF / 2) {
        return {INF, 0};
    }
    return {x.cost + add_cost, x.cnt + add_cnt};
}

bool row_ok(int up, int mid, int down, int full) {
    int cover = mid | up | down | ((mid << 1) & full) | (mid >> 1);
    return cover == full;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    int H, W;
    static long long w[55][8];
    if (n >= m) {
        H = n;
        W = m;
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                w[i][j] = a[i][j];
            }
        }
    } else {
        H = m;
        W = n;
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                w[i][j] = a[j][i];
            }
        }
    }

    int full = (1 << W) - 1;
    for (int i = 1; i <= H; i++) {
        for (int mask = 0; mask <= full; mask++) {
            cost_sum[i][mask] = 0;
            for (int b = 0; b < W; b++) {
                if (mask & (1 << b)) {
                    cost_sum[i][mask] += w[i][b + 1];
                }
            }
        }
    }

    for (int p = 0; p <= 1; p++) {
        for (int s1 = 0; s1 <= full; s1++) {
            for (int s2 = 0; s2 <= full; s2++) {
                dp[p][s1][s2] = {INF, 0};
            }
        }
    }

    // 处理完第 1 行后，上一行是 0，当前行是 cur，尚未检查第 1 行是否被下一行覆盖。
    for (int cur = 0; cur <= full; cur++) {
        dp[1][0][cur] = {cost_sum[1][cur], __builtin_popcount((unsigned int) cur)};
    }

    for (int row = 1; row < H; row++) {
        int now = row & 1;
        int nxt = now ^ 1;
        for (int s1 = 0; s1 <= full; s1++) {
            for (int s2 = 0; s2 <= full; s2++) {
                dp[nxt][s1][s2] = {INF, 0};
            }
        }

        for (int up = 0; up <= full; up++) {
            for (int mid = 0; mid <= full; mid++) {
                State cur_state = dp[now][up][mid];
                if (cur_state.cost >= INF / 2) {
                    continue;
                }
                for (int down = 0; down <= full; down++) {
                    if (!row_ok(up, mid, down, full)) {
                        continue;
                    }
                    State nxt_state = add_state(cur_state, cost_sum[row + 1][down],
                                                __builtin_popcount((unsigned int) down));
                    if (better(nxt_state, dp[nxt][mid][down])) {
                        dp[nxt][mid][down] = nxt_state;
                    }
                }
            }
        }
    }

    int last = H & 1;
    State ans = {INF, 0};
    for (int up = 0; up <= full; up++) {
        for (int mid = 0; mid <= full; mid++) {
            State cur_state = dp[last][up][mid];
            if (cur_state.cost >= INF / 2) {
                continue;
            }
            if (!row_ok(up, mid, 0, full)) {
                continue;
            }
            if (better(cur_state, ans)) {
                ans = cur_state;
            }
        }
    }

    cout << ans.cnt << ' ' << ans.cost << '\n';
    return 0;
}

复杂度

设压缩后宽度为 W，时间复杂度约为 $O(H * 2^{3W})$ ，空间复杂度 $O(2^{2W})$ 。

总结

这题本质上是网格上的带权最小支配集。真正让它可做的关键，是利用局部覆盖关系，把问题压成“三行判定、两行滚动”的轮廓 DP。

一图流解析

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