[ZJOI2007] 仓库建设

题意

每个工厂可以选择建仓库，也可以把货物往山下运到更低处的某个仓库。

总费用包含两部分：

建仓费用
按距离计算的运输费用

要求最小化总费用。

思路

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

const long long INF = (1LL << 62);
const int MAXN = 5005;

long long x[MAXN], p[MAXN], c[MAXN];
long long sum_p[MAXN], sum_px[MAXN];
long long dp[MAXN];
int n;

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

    // brute.cpp：小数据朴素 DP。
    // 直接枚举上一个建仓库的位置。
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> p[i] >> c[i];
        sum_p[i] = sum_p[i - 1] + p[i];
        sum_px[i] = sum_px[i - 1] + p[i] * x[i];
    }

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = INF;
        for (int j = 0; j < i; j++) {
            long long cost = dp[j]
                           + c[i]
                           + x[i] * (sum_p[i] - sum_p[j])
                           - (sum_px[i] - sum_px[j]);
            dp[i] = min(dp[i], cost);
        }
    }

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

设 dp[i] 表示前 i 个工厂全部处理完，并且最后一个仓库建在 i 的最小费用。

如果上一个仓库建在 j，那么 j+1..i 这些工厂的产品都运到 i。

利用前缀和：

sum_p[i] = p_1 + ... + p_i
sum_px[i] = p_1x_1 + ... + p_ix_i

则这一段的运输费用是：

x_i (sum_p[i] - sum_p[j]) - (sum_px[i] - sum_px[j])

于是：

dp[i] = min(dp[j] + c_i + x_i(sum_p[i]-sum_p[j]) - (sum_px[i]-sum_px[j]))

整理一下：

dp[i] = c_i + x_i sum_p[i] - sum_px[i] + min(dp[j] + sum_px[j] - x_i sum_p[j])

这就变成了标准斜率优化：

决策点 j 对应一条线
查询点是当前的 x_i

又因为：

x_i 单调递增
sum_p[j] 单调递增

所以可以直接用单调队列维护凸包。

DP 转移方程

核心状态：

dp[i] 为最后仓库建在 i 的最小费用

核心转移：

dp[i]=c_i+x_i*sum_p[i]-sum_px[i]+min(dp[j]+sum_px[j]-x_i*sum_p[j])

答案收束：

dp[n]

代码

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

const int MAXN = 1000005;

long long x[MAXN], p[MAXN], c[MAXN];
long long sum_p[MAXN], sum_px[MAXN];
long long dp[MAXN];
int q[MAXN];
int n;

long long X(int i) {
    return sum_p[i];
}

long long Y(int i) {
    return dp[i] + sum_px[i];
}

// 判断队头的后一个决策点是否已经在当前 x 下更优。
bool better_front(int a, int b, long long cur_x) {
    return (__int128) (Y(b) - Y(a)) <= (__int128) cur_x * (X(b) - X(a));
}

// 判断中间点 b 是否永远不会成为最优决策。
bool bad(int a, int b, int c) {
    return (__int128) (Y(b) - Y(a)) * (X(c) - X(b))
         >= (__int128) (Y(c) - Y(b)) * (X(b) - X(a));
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> p[i] >> c[i];
        sum_p[i] = sum_p[i - 1] + p[i];
        sum_px[i] = sum_px[i - 1] + p[i] * x[i];
    }

    int head = 1, tail = 1;
    q[1] = 0;
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        while (head < tail && better_front(q[head], q[head + 1], x[i])) {
            head++;
        }

        int j = q[head];
        // j 表示最后一个仓库建在 j 之后，下一个仓库建在 i。
        // 那么 j+1..i-1 的产品都运到 i。
        dp[i] = dp[j]
              + c[i]
              + x[i] * (sum_p[i] - sum_p[j])
              - (sum_px[i] - sum_px[j]);

        // 若斜率相同，只保留截距更小的那个决策点。
        while (head <= tail && X(q[tail]) == X(i)) {
            if (Y(q[tail]) <= Y(i)) {
                break;
            }
            tail--;
        }
        if (head <= tail && X(q[tail]) == X(i) && Y(q[tail]) <= Y(i)) {
            continue;
        }

        while (head < tail && bad(q[tail - 1], q[tail], i)) {
            tail--;
        }
        q[++tail] = i;
    }

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

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

这题的关键不是“建不建仓库”，而是看出：

每个仓库负责的一定是一段连续工厂。

一旦写成连续分段 DP，再把运输费用用前缀和展开，斜率优化就很自然了。

一图流解析

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