形式化题目

给定 $N$ 个位置 $0 = X_1 < X_2 < \dots < X_N$，每个位置 $i$ 有产品数 $P_i \geqslant 0$ 和建仓费用 $C_i \geqslant 0$。 选择一个下标集合 $S$ 建仓库，其余位置的产品只能运往编号更大的仓库。若 $i \notin S$， 令 $t(i)$ 为 $S$ 中大于 $i$ 的最小下标（因为 $t(N)$ 不存在，所以 $S$ 必须包含 $N$），则代价为

（每件产品运送 1 个单位距离费用为 1。）求这个代价的最小值。

把 $S$ 写为 $j_1 < j_2 < \dots < j_k = N$（另设哨兵 $j_0 = 0$），就得到等价表述：用若干连续段 $(j_{t-1}, j_t]$ 覆盖 $1 \dots N$，每段的产品全部运到段尾 $j_t$，求总代价最小。

正解

思路

先明确"每个工厂的产品去哪"。因为产品只能往编号更大的方向运，所以工厂 $i$ 的产品一定会 停在下游最近的那个仓库里——不可能越过一个仓库再往下送，那样只会多花运费。于是任何方案都把 工厂序列切成若干连续段，每段的产品运到段尾那个仓库。

设 $dp[i]$ 表示"前 $i$ 个工厂都处理完，且第 $i$ 个工厂一定建仓库"的最小费用，枚举上一个仓库 $j$：

用前缀和表示运费。记

则第 $(j, i)$ 段（不含端点 $j$，含 $i$ 之前的全部）的运费是

注意 $dp$ 的下标是"仓库位置"，所以运输费里出现的是 $W_{i-1}, D_{i-1}$：产品从 $j+1$ 到 $i-1$ 运过来， $i$ 自己的产品本来就在仓库里，运费为 0。（因为 $N$ 必须有仓库，答案就是 $dp[N]$； 第 $N$ 个工厂的产品也永远不会被运走。）

下面这张表用题面样例（$N=3$，$X=(0,5,9)$，$P=(5,3,6)$，$C=(10,100,10)$）把每个 $dp[i]$ 的 全部候选算出来。表中"运输费"列就是上面的公式，"$dp_j + \cdots$"列是候选值：

表的最后一行正好复现题面样例说明的两种方案：$j=0$ 表示只在工厂 3 建仓，运费 $9 \times 5 - 0 = 57$，总费用 $10 + 57 = 67$；$j=1$ 表示工厂 1、3 建仓，落在 $(1,3)$ 区间里的 工厂 2 把 3 件产品运到 9，运费 $9 \times (8-5) - (15-0) = 12$，总费用 $10 + 10 + 12 = 32$， 正是样例输出；$j=2$ 表示工厂 2、3 都建仓，没有运输费，但要付两次建仓费 $110 + 10 = 120$。 答案就是 $dp[N]$。

瓶颈：每个 $i$ 要枚举全部 $j < i$，共 $N(N-1)/2$ 次转移。$N = 10^6$ 时约 $5 \times 10^{11}$ 次， 必须消掉枚举。

线性化。把转移式里与 $j$ 有关的项单独拿出来，与 $i$ 有关的项提到 $\min$ 外面：

现在每个决策点 $j$ 对应一条直线 $y = m_j x + b_j$，而在 $i$ 处的代价就是 “这些直线在 $x = X_i$ 处的最小值”。这可以用下凸壳维护。把上面的样例继续算下去， 每条直线的参数与它在查询点上的取值是：

两条直线的交点在 $x = \frac{125-10}{8-5} = \frac{115}{3} \approx 38.3$，远大于查询点 $x_3 = 9$， 所以在 $x_3 = 9$ 上旧线 $-5x+10$ 仍然更小：新线留在凸壳上，但暂时不是队头（一旦后面的 $X_i$ 越过 $38.3$，队头就会自动移到新线上）。$dp_3$ 由队头取值加上只与 $i$ 有关的量得到：

为什么单调队列就够。本题有两个单调性：

1. 题面保证各厂位置递增，$X_1 < X_2 < \dots < X_N$，所以查询点单调不减： 队头某条线一旦不优于第二条，之后更不可能翻身，队头指针只前进、不回头。
2. $P_i \geqslant 0$ 使 $W_j = \sum_{t \leqslant j} P_t$ 单调不减，所以插入的斜率 $-W_j$ 单调不增： 新线永远插在凸壳尾部，队尾只需检查"最后一条线的生效区间是否被新交点截空"。

两个条件都满足，于是不需要二分、不需要平衡树，凸壳用一条"队尾 append/pop、 队头用下标推进"的单调队列即可，每条直线最多进出一次，均摊 $O(1)$。

实现上还有两点：转移只依赖 $dp[i-1]$，所以不用保存整张 $dp$ 表，一个变量滚动即可； $W, D$ 也是边读边累加的，因此连 $X, P, C$ 数组都不用存。判据用交叉相乘代替除法：两条旧线的 交点横坐标是 $x_{12}=\tfrac{b_2-b_1}{m_1-m_2}$，末线与新线的交点是 $x_{23}=\tfrac{b-b_2}{m_2-m}$， 当 $x_{12} \geqslant x_{23}$ 时末线被完全盖住。斜率单调不增即 $m_1 \geqslant m_2 \geqslant m$： 严格递减时两个分母都为正，两边同乘 $(m_1-m_2)(m_2-m)$（仍是正数）得到代码里的整数比较 (b2 - b1) * (m2 - m) >= (b - b2) * (m1 - m2)；出现相等斜率时，同一判据恰好退化为 “保留截距较小的那条直线”，结论不变。整个过程不做除法，没有浮点误差。

代码

Python 版：

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 21:59
# update_at: 2026-09-30 21:59

import sys
from collections.abc import Iterator


def read_ints() -> Iterator[int]:
    """按块解码输入：一次 read() 全读再 split() 会同时留下 25 MB 字节和 300 万个 token 对象。"""
    stream = sys.stdin.buffer
    tail = b""
    while block := stream.read(1 << 20):
        body, _, tail = (tail + block).rpartition(b"\n")  # 末行可能被切断，留给下一块拼
        yield from map(int, body.split())
    yield from map(int, tail.split())


def solve() -> None:
    data = read_ints()
    n = next(data)

    # 凸壳用「队尾 list.append/list.pop + 队头指针 h」实现，两个数是斜率 m 和截距 b。
    slope: list[int] = []
    intercept: list[int] = []
    head = 0
    # 前缀量边读边更新：W = W[i-1] = sum_{t<i} P_t，D = D[i-1] = sum_{t<i} P_t*X_t；
    # best = dp[i-1]，即「前 i-1 个工厂处理完且第 i-1 个建仓」的最小费用。
    W = D = best = 0

    for _ in range(n):
        x, p, c = next(data), next(data), next(data)

        # dp[j] 对应的直线 y = -W[j]*x + dp[j] + D[j]，新直线永远接在队尾
        m, b = -W, best + D
        while len(slope) - head >= 2:
            # 两条旧直线的交点横坐标 x12 与末条、新直线的交点 x23：x12 >= x23 时末条永不为最小
            x12 = (intercept[-1] - intercept[-2]) * (slope[-1] - m)
            x23 = (b - intercept[-1]) * (slope[-2] - slope[-1])
            if x12 < x23:
                break
            slope.pop()
            intercept.pop()
        slope.append(m)
        intercept.append(b)

        while len(slope) - head >= 2:
            # 查询点 x 单调不减：队头一旦不优于第二条，之后也不会翻身
            if slope[head] * x + intercept[head] < slope[head + 1] * x + intercept[head + 1]:
                break
            head += 1

        best = c + x * W - D + slope[head] * x + intercept[head]  # dp[i]
        W += p
        D += p * x

    print(best)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:44
 * update_at: 2026-10-05 12:50
 */
// ZJOI 2007 仓库建设：分段 DP + 斜率优化（单调队列维护下凸壳），O(N)。
// dp[i]：前 i 个工厂处理完且第 i 个建仓库的最小费用；产品只能往编号更大的方向运。
#include <cstdio>

typedef long long ll;

const int MAXN = 1000005;

// 每个工厂：位置、产品数、建仓费（N 最大 1e6，开全局数组避免爆栈）
ll x[MAXN];
ll p[MAXN];
ll c[MAXN];

// 下凸壳用数组模拟队列：slope/intercept 保存每条决策直线 y = m*x + b
// 决策点 j（dp[j]，j 可为 0 哨兵）对应斜率 m = -W[j]，截距 b = dp[j] + D[j]
ll q_slope[MAXN];
ll q_intercept[MAXN];
int head = 0; // 队头下标，只前进
int tail = 0; // 队尾下标（开区间），新直线插在 tail 处

ll w_sum[MAXN]; // w_sum[j] = P_1 + ... + P_j（前缀和，W[j]）
ll d_sum[MAXN]; // d_sum[j] = P_1*X_1 + ... + P_j*X_j（前缀和，D[j]）
ll dp[MAXN];    // dp[i]：第 i 个工厂一定建仓库时的最小费用，dp[0] = 0

// 把决策点（斜率 m、截距 b）加入队尾
// 队列内斜率严格递减：先消掉与末线平行的情形（P 可为 0，W 不严格递增），再弹被盖住的末线
void push_line(ll m, ll b) {
    // 斜率相同时两条平行线只剩截距更小的一条
    while (tail > head && q_slope[tail - 1] == m) {
        if (b >= q_intercept[tail - 1]) return; // 新线永不更优，直接丢弃
        tail--;
    }
    while (tail - head >= 2) {
        // 末线被盖住 <=> 旧两线交点横坐标 x12 >= 末线与新线交点横坐标 x23
        // x12 = (b_last - b_prev) / (m_prev - m_last)，x23 = (b - b_last) / (m_last - m)
        // 此时两个分母都为正（斜率严格递减），交叉相乘避免除法
        if ((q_intercept[tail - 1] - q_intercept[tail - 2]) * (q_slope[tail - 1] - m)
                >= (b - q_intercept[tail - 1]) * (q_slope[tail - 2] - q_slope[tail - 1]))
            tail--;
        else
            break;
    }
    q_slope[tail] = m;
    q_intercept[tail] = b;
    tail++;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld %lld", &x[i], &p[i], &c[i]);
    }

    // 哨兵决策点 j = 0：dp[0] = 0，W[0] = D[0] = 0，对应直线 y = 0（截距 0）
    dp[0] = 0;
    w_sum[0] = 0;
    d_sum[0] = 0;
    head = tail = 0;
    push_line(0, 0);

    for (int i = 1; i <= n; i++) {
        // 转移：dp[i] = c[i] + x[i]*W[i-1] - D[i-1] + min_j { -W[j]*x[i] + dp[j] + D[j] }
        // 推导：(j, i] 段运费 = x[i]*(W[i-1]-W[j]) - (D[i-1]-D[j])，i 自己的产品运费为 0

        // 查询点 x[i] 单调递增：队头一旦不优于第二条，之后也不会翻身
        while (tail - head >= 2
                && q_slope[head] * x[i] + q_intercept[head]
                   >= q_slope[head + 1] * x[i] + q_intercept[head + 1])
            head++;

        ll best = q_slope[head] * x[i] + q_intercept[head]; // min 部分取到的是 dp[j] + D[j]
        dp[i] = c[i] + x[i] * w_sum[i - 1] - d_sum[i - 1] + best;

        // 插入新决策点 j = i：W 单调不减 => 斜率 -W[i] 单调不增，永远插在队尾
        w_sum[i] = w_sum[i - 1] + p[i];       // W[i] = sum_{t<=i} P_t
        d_sum[i] = d_sum[i - 1] + p[i] * x[i]; // D[i] = sum_{t<=i} P_t*X_t
        push_line(-w_sum[i], dp[i] + d_sum[i]);
    }

    // 题面保证产品运往山脚工厂 N，所以 S 必须包含 N，答案就是 dp[N]
    printf("%lld\n", dp[n]);
    return 0;
}

复杂度

• 时间复杂度：$O(N)$。外层扫描 $N$ 次，凸壳中每条直线最多入队、出队各一次，均摊 $O(1)$。
• 空间复杂度：$O(N)$，只用于两棵凸壳数组 slope / intercept；$W, D, dp$ 都是单个标量。 读入按 1 MiB 分块处理，避免一次性留下全部 token。

总结

• 关键第一步是看清方案的形状：产品只能往山下运，所以每个仓库承接的必然是一段连续工厂， 问题化为"把 $1 \dots N$ 切段、段内运到段尾"的一维线性 DP。
• 第二步是前缀和展开：把段运费写成 $X_i(W_{i-1}-W_j) - (D_{i-1}-D_j)$， 于是与 $j$ 有关的只剩 $-W_j X_i + D_j$。
• 第三步是斜率优化：$dp[i] = C_i + X_i W_{i-1} - D_{i-1} + \min_j\{-W_j X_i + dp[j]+D_j\}$， 决策点变成直线，查询变成"$x = X_i$ 处取最小"。
• 因为 $X_i$ 递增、$W_j$ 递增，查询点与斜率都单调，单调队列凸壳就能 $O(N)$ 解决； 判据用整数乘法，无精度问题。
• 本题必须建工厂 $N$ 的仓库，这一点已经写进 $dp[N]$ 的定义里；$N = 1$ 时答案为 $C_1$。

图示解析

把上面的推导压缩成一条路线，方便读完后复盘：

flowchart TD
    A["朴素分段 DP：<br/>dp[i] = c_i + min_j（dp[j] + 段运费）"] --> B["前缀和展开段运费：<br/>W[k] = ΣP，D[k] = ΣP·X"]
    B --> C["与 i 有关的项提到 min 外：<br/>dp[i] = c_i + X_i·W[i-1] - D[i-1]<br/>+ min_j ( -W[j]·X_i + dp[j] + D[j] )"]
    C --> D["每个决策点 j 变成一条直线<br/>斜率 m_j = -W[j]，截距 b_j = dp[j] + D[j]"]
    D --> E["两个单调性：<br/>查询点 X_i 递增、斜率 -W[j] 不增"]
    E --> F["查询：队头指针只前进<br/>均摊 O(1)"]
    E --> G["插入：队尾弹掉被新线盖住的直线<br/>均摊 O(1)"]
    F --> H["总复杂度 O(n)"]
    G --> H

图中上半部分是建模与化简：先有分段 DP，再用前缀和把转移拆成"只与 $i$ 有关"和"若干直线在 $X_i$ 处的最小值"。下半部分是数据结构的依据：两个单调性分别让查询和插入都只需要移动指针， 不需要二分与平衡树，最终把 $O(N^2)$ 降到 $O(N)$。