四边形不等式优化DP-学习笔记

Part 1: 问题分析与关键的子问题#

首先，我们来分析一下题目。要把 P 个邮局放在 V 个村庄里（或旁边），让每个村庄到最近邮局的距离总和最小。

村庄都在一条直线上，这是一个非常重要的性质。为了方便处理，我们的第一步应该是将所有村庄的坐标排序。设排序后的坐标为 $x_1,x_2,\ldots,x_V$。

一个至关重要的结论是：每个邮局负责的村庄，在排好序的序列中，一定是连续的一段。 为什么呢？如果村庄 i 和 k (i < k) 都去邮局 A，而它们中间的村庄 j (i < j < k) 却去了更远的邮局 B，那还不如让村庄 j 也去邮局 A，总距离一定会更小。

所以，问题转化成了：将 V 个村庄分成 P 个连续的段，为每一段设立一个邮局，使得总距离和最小。

那么，这就引出了一个子问题：

子问题： 如果我们决定用一个邮局服务第 i 个到第 j 个村庄，这个邮局应该建在哪里，才能使这段村庄的距离和最小？这个最小的距离和是多少？

这是一个经典的“货仓选址”问题。

# 货仓选址

对于一条直线上的点集 $x_i,x_i+1,\ldots,x_j$，要找一个点 y 使得 $sum_k=\sum_{k = i}^{j}∣x_k−y∣$ 最小，最优的 y 点应该选在这些点的中位数位置上。

对于已经排好序的村庄 $x_i,\ldots,x_j$，中位数就是 $x_m$，其中 $m=\lfloor\frac{i+j}{2}\rfloor$。

因此，我们就定义一个代价函数 $w(i,j)$：表示用一个邮局服务第 i 到第 j 个村庄的最小距离和。这个邮局会建在第 $\lfloor\frac{i+j}{2}\rfloor$ 个村庄的位置上。

好的，现在我们有了代价函数 $w(i,j)$。我们需要高效地计算出所有可能的 $w(i,j)$。如果每次都暴力计算，总共需要 $O(V^3)$ 的时间，太慢了。我们可以通过预处理坐标的前缀和，在 $O(1)$ 时间内计算出 $w(i,j)$。

设 $S[k]=sum_{l=1}^{k}x_l$ 是坐标的前缀和。则 $w(i,j)$ 的值为：

这样，预处理前缀和 $S$ 需要 $O(V)$，然后便可在 $O(1)$ 时间内计算出 $w(i, j)$。

Part 2: 建立 DP 模型#

解决了子问题，我们就可以开始构建主 DP 模型了。我们要用 P 个邮局划分 V 个村庄。

第一步：定义状态

我们需要知道“已经处理了多少村庄”和“已经用了多少邮局”。所以，一个很自然的状态定义是： dp[i][j] 表示用 i 个邮局，覆盖前 j 个村庄的最小总距离和。 我们的目标就是求 dp[P][V]。

第二步：状态转移

现在我们来思考如何计算 dp[i][j]。 根据定义，我们要用 i 个邮局覆盖前 j 个村庄。我们可以把第 i 个邮局（也就是最后一个邮局）单独拿出来考虑。假设它负责的村庄区间是 $[k+1,j]$，那么剩下的前 k 个村庄就必须由 i-1 个邮局来负责。

这个分割点 k 可以在 $0$ 到 $j−1$ 之间取值（但为了保证有 i - 1 个邮局能放下，k 至少要等于 i - 1）。 于是，状态转移方程就诞生了：

$dp[i][j]=\min_{i−1≤k<j}​{dp[i−1][k]+w(k+1,j)}$

这个方程的边界是什么呢？

• $dp[1][j] = w(1,j)$，表示用 1 个邮局覆盖前 j 个村庄的代价。
• $dp[i][i]=0$，表示用 i 个邮局覆盖前 i 个村庄，每个村庄都建一个邮局，距离和为 0。

这个 DP 的时间复杂度是 $O(P\cdot V^2)$（i 循环 P 次，j 循环 V 次，k 循环 V 次）。对于 $V=3000$, $P=300` 的数据，这个复杂度是无法接受的，必须优化！

Part 3: 四边形不等式登场！#

这个 DP 方程 $dp[i][j]=\min_{i−1≤k<j}​{dp[i−1][k]+w(k+1,j)}$ 的形式和我们之前讨论的优化形式非常相似！这种形式的 DP 方程，如果代价函数 $w(i,j)$ 满足四边形不等式，就存在决策单调性，可以优化。

四边形不等式定义：对于任意 $a\le b\le c\le d$，有 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$。

一个重要的结论：可以证明（但过程很复杂，我们一般直接作为结论使用），本题中定义的代价函数 $w(i,j)$（即区间内所有点到中位数的距离和）是满足四边形不等式的。

决策单调性： 如果 $w$ 满足四边形不等式，那么 DP 的最优决策点就会有单调性。记 $s[i][j]$ 为计算 $dp[i][j]$ 时，取得最小值的那个 k。那么 $s[i][j]$ 满足：

这个不等式是优化的关键！它告诉我们：

1. $s[i][j]\le s[i][j+1]$：对于固定的邮局数 i，覆盖的村庄数 j 越多，最优的分割点 k 也会越靠后（或不变）。
2. $s[i−1][j]\le s[i][j]$：对于固定的村庄数 j，使用的邮局数 i 越多，最后一个邮局的分割点 k 也会越靠后（或不变）。这很直观，因为邮局多了，最后一个邮局需要负责的村庄就变少了。

Part 4: $O(PV)$ 优化实现#

根据决策单调性 $s[i−1][j]\le s[i][j]\le s[i][j+1]$，我们在计算 $dp[i][j]$ 时，对最优分割点 k 的搜索范围就可以从 $[i−1,j−1]$ 缩小到 $[s[i−1][j],s[i][j+1]]$。

我们来看看新的循环结构：

1
// ... 初始化 dp[1][j] 和 s[1][j]
2
for (int i = 2; i <= P; ++i) {
3
    // 关键点：j 需要倒序循环
4
    for (int j = V; j >= i; --j) {
5
        int lower_k = s[i - 1][j];
6
        // s[i][j+1] 在 j 的上一次循环 (j+1) 中已经被计算出来了
7
        int upper_k = (j == V) ? (V - 1) : s[i][j + 1];
8

9
        for (int k = lower_k; k <= upper_k; ++k) {
10
            // ... 更新 dp[i][j] 和 s[i][j]
11
        }
12
    }
13
}

为什么 j 需要倒序循环？ 因为在计算 dp[i][j] 时，我们需要用到 s[i][j+1] 作为 k 的搜索上界。如果我们正序循环 j，那么在算 dp[i][j] 时，s[i][j+1] 还是未知的。而倒序循环 j，在计算 j 时，j+1 的所有信息都已经计算完毕了，就可以放心使用。

复杂度分析 这个优化后的时间复杂度是多少呢？ 对于固定的 i，j 从 V 循环到 i。k 的总循环次数大约是：

可以证明（通过上一题讲过的伸缩和），对于每个 i，j 和 k 的总循环次数是 $O(V)$ 的。 外层还有一个 i 从 2 到 P 的循环，所以 DP 部分的总时间复杂度是 $O(P\cdot V)$。

加上预处理 $w(i,j)$ 的 $O(V^2)$，最终总时间复杂度为 $O(V^2+PV)$，对于本题的数据范围来说，已经足够快了！

下面是完整的代码实现，主人可以参考一下~

Part 5: 代码实现#

下面是完整的代码实现：

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
int main() {
6
    ios::sync_with_stdio(false);
7
    cin.tie(nullptr);
8

9
    int V, P;
10
    cin >> V >> P;
11

12
    vector<int> a(V);
13
    for (int i = 0; i < V; i++) {
14
        cin >> a[i];
15
    }
16

17
    // 计算坐标前缀和，用于快速计算 w(i,j)
18
    vector<i64> pre(V + 1, 0);
19
    for (int i = 0; i < V; i++) {
20
        pre[i + 1] = pre[i] + a[i];
21
    }
22

23
    // 代价函数 w(i,j)：用一个邮局服务区间 [i,j] 的最小距离和
24
    // 邮局建在中位数位置 m = (i+j)/2
25
    auto w = [&](int i, int j) {
26
        int m = (i + j) >> 1;  // 中位数位置
27
        // 利用前缀和快速计算距离和
28
        return 1LL * (2 * m - (i + j) + 1) * a[m] - (pre[m + 1] - pre[i]) + (pre[j + 1] - pre[m + 1]);
29
    };
30

31
    // dp[i][j]: 用 i 个邮局覆盖前 j 个村庄的最小距离和
32
    vector<vector<i64>> dp(P + 1, vector<i64>(V + 1, 1e18));
33
    // s[i][j]: 计算 dp[i][j] 时的最优分割点 k
34
    vector<vector<int>> s(P + 1, vector<int>(V + 2, 0));
35

36
    // 初始状态：0 个邮局覆盖 0 个村庄，距离为 0
37
    dp[0][0] = 0;
38

39
    for (int i = 1; i <= P; i++) {
40
        // 边界处理：s[i][V+1] = V，作为最后一个分割点的上界
41
        s[i][V + 1] = V;
42

43
        // 倒序循环 j，确保计算 dp[i][j] 时 s[i][j+1] 已知
44
        for (int j = V; j >= i; j--) {
45
            // 利用决策单调性缩小搜索范围
46
            int lo = s[i - 1][j];      // 下界：来自 s[i-1][j] ≤ s[i][j]
47
            int hi = s[i][j + 1];      // 上界：来自 s[i][j] ≤ s[i][j+1]
48

49
            // 在缩小的范围内搜索最优分割点 k
50
            for (int k = lo; k <= min(hi, j - 1); k++) {
51
                // 尝试用前 k 个村庄放 i-1 个邮局，第 i 个邮局负责 [k+1, j]
52
                if (i64 res = dp[i - 1][k] + w(k, j - 1); res < dp[i][j]) {
53
                    dp[i][j] = res;
54
                    s[i][j] = k;  // 记录最优分割点
55
                }
56
            }
57
        }
58
    }
59

60
    // 输出最终答案：P 个邮局覆盖 V 个村庄的最小距离和
61
    cout << dp[P][V] << "\n";
62

63
    return 0;
64
}