[IOI 2000] 邮局加强版

题意

一条数轴上有 V 个村庄，位置已知，要在其中一些村庄上建 P 个邮局。

每个村庄会去离自己最近的邮局，要求所有村庄到最近邮局的距离和最小。

思路

先看一个可以直接验证想法的朴素解：

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

const int INF = 0x3f3f3f3f;

int v, p;
int x[35];
int cost[35][35];
int dp[35][35];

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

    cin >> v >> p;
    for (int i = 1; i <= v; i++) {
        cin >> x[i];
    }
    sort(x + 1, x + v + 1);

    for (int l = 1; l <= v; l++) {
        for (int r = l; r <= v; r++) {
            int mid = (l + r) >> 1;
            for (int i = l; i <= r; i++) {
                cost[l][r] += abs(x[i] - x[mid]);
            }
        }
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;

    for (int k = 1; k <= p; k++) {
        for (int i = 1; i <= v; i++) {
            for (int j = 0; j < i; j++) {
                dp[k][i] = min(dp[k][i], dp[k - 1][j] + cost[j + 1][i]);
            }
        }
    }

    cout << dp[p][v] << '\n';
    return 0;
}

先把村庄位置排序。

如果一段连续村庄 [l, r] 只建一个邮局，最优位置一定在中位数村庄。

所以可以先预处理：

cost[l][r]：负责区间 [l, r] 的所有村庄时，只建一个邮局的最小总代价

接下来做 DP。

设：

dp[k][i]：前 i 个村庄建 k 个邮局时的最小总代价

最后一个邮局负责区间 [j+1, i]，则有转移：

dp[k][i] = min(dp[k-1][j] + cost[j+1][i])

朴素枚举 j 的复杂度是 $O(PV^2)$ ，这里会超时。

这题满足决策单调性，可以用分治优化。

也就是说：

dp[k][i] 的最优决策点
不会在 i 变大时向左跳

于是每一层 k 的 DP，都可以用一次分治递归在 $O(V log V)$ 次状态里完成，每个状态只在一个较小的决策区间里找最优值。

所以整体就能通过 V <= 3000 的数据。

DP 转移方程

核心状态：

dp[k][i] 为前 i 村建 k 个邮局的最小代价

核心转移：

dp[k][i]=min_j dp[k-1][j]+cost[j+1][i]

答案收束：

dp[P][V]

代码

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

const int MAXN = 3005;
const int MAXP = 305;
const int INF = 0x3f3f3f3f;

int v, p;
int x[MAXN];
int cost[MAXN][MAXN];
int dp[MAXP][MAXN];

// 分治优化：
// 计算 dp[layer][l..r]，最优决策点在 [opt_l, opt_r] 中。
void solve_layer(int layer, int l, int r, int opt_l, int opt_r) {
    if (l > r) {
        return;
    }

    int mid = (l + r) >> 1;
    int best_k = -1;
    dp[layer][mid] = INF;

    int right = min(mid - 1, opt_r);
    for (int k = opt_l; k <= right; k++) {
        int val = dp[layer - 1][k] + cost[k + 1][mid];
        if (val < dp[layer][mid]) {
            dp[layer][mid] = val;
            best_k = k;
        }
    }

    solve_layer(layer, l, mid - 1, opt_l, best_k);
    solve_layer(layer, mid + 1, r, best_k, opt_r);
}

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

    cin >> v >> p;
    for (int i = 1; i <= v; i++) {
        cin >> x[i];
    }
    sort(x + 1, x + v + 1);

    // 预处理一段区间只建一个邮局时的最小总代价。
    // 最优邮局位置是中位数点。
    for (int l = v; l >= 1; l--) {
        for (int r = l; r <= v; r++) {
            int mid = (l + r) >> 1;
            cost[l][r] = cost[l][r - 1] + x[r] - x[mid];
        }
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 1; i <= v; i++) {
        dp[1][i] = cost[1][i];
    }

    for (int layer = 2; layer <= p; layer++) {
        solve_layer(layer, layer, v, layer - 1, v - 1);
    }

    cout << dp[p][v] << '\n';
    return 0;
}

复杂度

预处理 cost 是 $O(V^2)$ 。

DP 分治优化总复杂度大致是 $O(PV log V)$ 。

空间复杂度是 $O(PV + V^2)$ 。

总结

这题是经典“邮局问题”。

核心分两步：

先把“一段村庄只建一个邮局”的代价预处理出来
再把多邮局问题写成分层 DP，并利用决策单调性优化

理解这题之后，很多“四边形不等式 / 决策单调性”的 DP 都会更容易上手。

一图流解析

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