形式化题目

沿直线从山顶到山脚种着 $n$ 棵树，树 $i$ 重量为 $w_i$；$d_i$ 是树 $i$ 与树 $i+1$ 的间距，$d_n$ 是树 $n$ 到山脚的距离。记

山脚已有一个锯木厂，还要在山路上恰好新修两个。木材只能向山下运，每棵树由它下游方向最近的那个锯木厂承接；每公斤每米运费 1 分。求所有新厂位置中总运费的最小值。

样例（$n=9$）：

1
2
3山顶
 │
 1(1)─2─2(2)─1─3(3)★─3─4(1)─1─5(3)─2─6(1)★─6─7(2)─1─8(1)─2─9(1)─1→山脚锯木厂

图中 树号(重量)，连线上的数字是间距，★ 是最优的两个新厂。运费分三段：树 1…3 运到 $pos=3$ 的厂得 $1{\times}3+2{\times}1+3{\times}0=5$，树 4…6 运到 $pos=9$ 的厂得 $1{\times}3+3{\times}2+1{\times}0=9$，树 7…9 运到山脚 $pos=19$ 得 $2{\times}4+1{\times}3+1{\times}1=12$，合计 $5+9+12=26$。

正解

思路

1. 方案的形状：归一化到树位置。 承接「最低一棵树 $b$」的厂，其费用 $\sum_k w_k(p-pos_k)$ 关于位置 $p$ 单调不减，而它必须放在 $p \geqslant pos_b$ 处，所以放 $p = pos_b$（树 $b$ 处）最优——新厂只需考虑建在树下。又因为木材只能下行，每个厂承接的必然是一段连续的树：若两个新厂位于树 $j < i$，则树 $1..j$ 运到厂 $j$、树 $j{+}1..i$ 运到厂 $i$、树 $i{+}1..n$ 运到山脚厂。

2. 朴素 DP。 记前缀和

则三段运费分别是

固定较低的厂 $i$，把「上一个厂 $j$」作为决策，定义 $f[i]=\min_{j<i}\{C_1(j)+C_2(j,i)\}$，最后

（$i\geqslant 2$ 因为较低的厂必须在较高的厂下游；$i=n$ 时尾段为空 $C_3=0$）。每个 $f[i]$ 枚举 $i-1$ 个 $j$，总 $O(n^2)$；$n=2\times10^5$ 时约 $2\times10^{10}$ 次转移，这是瓶颈。

3. 线性化：转移是直线族取最小。 把 $C_1(j)+C_2(j,i)$ 整体展开，按「含 $j$ / 不含 $j$」分组（$-swd[j]$ 与 $+swd[j]$ 相消）：

$\min$ 里每个决策 $j$ 对应一条直线 $y_j(x)=m_jx+b_j$，问题变成「若干条固定直线在 $x=pos_i$ 处取最小值」，可用下凸壳维护。

4. 为什么单调队列就够（双单调）。 本题有两个单调性：

• $w_k\geqslant 1$ ⇒ $sw[j]$ 严格递增 ⇒ 斜率 $m_j=-sw[j]$ 严格递减：新直线永远从壳尾进入，队尾只需判断末线是否被新线完全盖住；
• $d_i\geqslant 0$ ⇒ $pos_i$ 单调不减 ⇒ 查询点单调：队头某条线一旦输给下一条，之后不可能翻身，队头指针只前进。

两个条件同时成立，凸壳两端都只移动指针，每条直线入队、出队各一次，均摊 $O(1)$，不需要二分或平衡树。判据用交点交叉相乘做整数比较，全程无浮点误差。

下面用样例展示每个 $i$ 的转移结果（$f[6]$ 的候选值依次为 $j=1..5$：$41,\ 29,\ 14,\ 29,\ 30$）：

表中每行是「第二个厂建在树 $i$」时的最优代价，列含义依次为：转移最小值、达到最小值的上一个厂 $j$、树 $i{+}1..n$ 运到山脚的费用、二者之和。最小值 $26$ 出现在 $i=6$、$j=3$，正是形式化题目里 ★ 的方案；而 $i=7,8$ 时尾段更短但前两段运费更高，说明必须同时权衡三段，不能贪心地让某个厂独吞下游。

5. 实现要点。 边读入边推进 $pos$（读完第 $i$ 行的 $d_i$ 后 pos += d 恰好得到 $pos_{i+1}$，读完最后一行即山脚 $pos_{n+1}$）；对每个 $i\geqslant 2$ 先用队头算 $f[i]$，再入队直线 $(-sw[i],\ sw[i]pos_i)$，保证查询只用 $j<i$；读完全部数据后再逐个加 $C_3(i)$ 取最小。

代码

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
65
66#!/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 22:40
# update_at: 2026-09-30 22:40

import sys
from collections import deque


def hull_add(hull: deque, slope: int, intercept: int) -> None:
    """把直线 y = slope*x + intercept 并入下凸壳（直线按斜率递减顺序入队）。

    若「尾前直线与尾直线」的交点不小于「尾直线与新直线」的交点，尾直线
    在所有位置都被新直线压住，出队。交点横坐标之比用交叉相乘判断，避免除法。
    """
    while len(hull) >= 2:
        m1, c1 = hull[-2]
        m2, c2 = hull[-1]
        # 交点 x(l1,l2) = (c2-c1)/(m1-m2)，两条分母都为正，可直接交叉相乘
        if (c2 - c1) * (m2 - slope) >= (intercept - c2) * (m1 - m2):
            hull.pop()
        else:
            break
    hull.append((slope, intercept))


def hull_query(hull: deque, x: int) -> int:
    """查询凸壳在横坐标 x 处的最小值：查询点单调不减，最优直线只向队尾移动。"""
    while len(hull) >= 2 and hull[0][0] * x + hull[0][1] >= hull[1][0] * x + hull[1][1]:
        hull.popleft()
    return hull[0][0] * x + hull[0][1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    # sw[i] = 前 i 棵树总重量；swd[i] = 前 i 棵树的 Σ w_k·pos_k；
    # f[i] = 两个新锯木厂中较高的在树 j<i、较低的建在树 i 时，树 1..i 的最小运费
    sw: list[int] = [0] * (n + 1)
    swd: list[int] = [0] * (n + 1)
    f: list[int] = [0] * (n + 1)

    hull: deque = deque()  # 直线 y = -sw[j]·x + sw[j]·pos_j，斜率随 j 递减
    pos = 0                # 当前树到山顶的距离 pos_i，山顶处 pos_1 = 0
    for i in range(1, n + 1):
        w, d = next(data), next(data)
        sw[i], swd[i] = sw[i - 1] + w, swd[i - 1] + w * pos

        # f[i] = sw[i]·pos_i - swd[i] + min_j ( sw[j]·pos_j - sw[j]·pos_i )
        # min 部分恰是候选直线族在 x = pos_i 处的最小值，用凸壳 O(1) 取到
        if i > 1:
            f[i] = sw[i] * pos - swd[i] + hull_query(hull, pos)

        hull_add(hull, -sw[i], sw[i] * pos)  # 树 i 成为「较高锯木厂」的候选
        pos += d                             # 推进到下一棵树，读完 d_n 后即山脚

    # 第二个锯木厂在树 i 时，树 i+1..n 全部运到山脚锯木厂的费用
    tail = [(sw[n] - sw[i]) * pos - (swd[n] - swd[i]) for i in range(n + 1)]
    print(min(f[i] + tail[i] for i in range(2, n + 1)))


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/**
 * 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 23:02
 * update_at: 2026-10-05 23:03
 */
#include <iostream>
using namespace std;

const int MAXN = 200005;

typedef long long ll;

ll n;
ll sw[MAXN];   // sw[i] = 前 i 棵树的总重量
ll swd[MAXN];  // swd[i] = 前 i 棵树的 Σ w_k·pos_k
ll f[MAXN];    // f[i] = 较低的厂建在树 i 时，树 1..i 的最小运费（较高的厂在其上游）

// 下凸壳，维护若干条直线 y = m·x + b，按斜率递减的顺序存放
ll hull_m[MAXN]; // 候选直线的斜率 m_j = -sw[j]
ll hull_b[MAXN]; // 候选直线的截距 b_j = sw[j]·pos_j
int head_pos;    // 队头指针：查询点单调不减，只前进
int tail_pos;    // 队尾指针：新直线从队尾进入

// 把直线 y = s·x + b 加入下凸壳（斜率 s 比壳内所有直线都小）
void hull_add(ll s, ll b) {
    // 若「尾前直线 l1 与尾直线 l2」的交点不低于「尾直线 l2 与新直线 l3」的交点，
    // 则 l2 被完全压住，弹出。交点比较用交叉相乘，避免除法与浮点。
    while (tail_pos - head_pos >= 2) {
        ll m1 = hull_m[tail_pos - 2], c1 = hull_b[tail_pos - 2];
        ll m2 = hull_m[tail_pos - 1], c2 = hull_b[tail_pos - 1];
        // x(l1,l2) = (c2-c1)/(m1-m2)，x(l2,l3) = (b-c2)/(m2-s)，两条分母都为正
        if ((c2 - c1) * (m2 - s) >= (b - c2) * (m1 - m2)) {
            tail_pos--;
        } else {
            break;
        }
    }
    hull_m[tail_pos] = s;
    hull_b[tail_pos] = b;
    tail_pos++;
}

// 查询凸壳在横坐标 x 处的最小值
ll hull_query(ll x) {
    while (tail_pos - head_pos >= 2 &&
           hull_m[head_pos] * x + hull_b[head_pos] >=
               hull_m[head_pos + 1] * x + hull_b[head_pos + 1]) {
        head_pos++;
    }
    return hull_m[head_pos] * x + hull_b[head_pos];
}

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

    cin >> n;

    ll pos = 0; // 当前树到山顶的距离 pos_i，山顶处 pos_1 = 0
    for (ll i = 1; i <= n; i++) {
        ll w, d;
        cin >> w >> d;
        sw[i] = sw[i - 1] + w;
        swd[i] = swd[i - 1] + w * pos;

        // f[i] = sw[i]·pos_i - swd[i] + min_{j<i} ( sw[j]·pos_j - sw[j]·pos_i )
        // 后一项是候选直线族在 x = pos_i 处的最小值，用下凸壳 O(1) 取得
        if (i > 1) {
            f[i] = sw[i] * pos - swd[i] + hull_query(pos);
        }

        hull_add(-sw[i], sw[i] * pos); // 树 i 成为「较高的厂」的候选
        pos += d;                      // 推进到下一棵树，读完 d_n 后即山脚
    }

    // 循环结束时 pos = pos_{n+1}（山脚）。尾段：树 i+1..n 全部运到山脚的费用
    ll ans = -1;
    for (ll i = 2; i <= n; i++) {
        ll tail_cost = (sw[n] - sw[i]) * pos - (swd[n] - swd[i]);
        ll total = f[i] + tail_cost;
        if (ans < 0 || total < ans) {
            ans = total;
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

• 时间复杂度：$O(n)$。一次线性扫描，凸壳中每条直线最多入队、出队各一次，均摊 $O(1)$。对比朴素 DP 的 $O(n^2)$，$n=2\times10^5$ 时从约 $2\times10^{10}$ 次运算降到 $2\times10^5$ 次。
• 空间复杂度：$O(n)$。sw、swd、f、tail 各一个长度 $n{+}1$ 的数组（$n=2\times10^5$ 时实测峰值约 85 MB，在 128 MB 内），凸壳最多存 $n$ 条直线。

总结

• 运费模型的关键是连续三段：木材只能下行 ⇒ 每个厂承接一段连续的树 ⇒ 枚举「较低厂 $i$ + 上一个厂 $j$」覆盖全部方案，得到以 $j$ 为决策的一维 DP。
• 前缀和展开是线性化的前提：$C_1+C_2$ 中所有含 $j$ 的项恰好凑成 $-sw[j]\,pos_i + sw[j]\,pos_j$，即一条斜率为 $-sw[j]$、截距为 $sw[j]pos_j$ 的直线在 $x=pos_i$ 处的值。
• 双单调（斜率递减、查询点不减）让下凸壳退化为单调队列，队头队尾各一个指针，均摊 $O(1)$；判据用整数交叉相乘，无精度隐患。
• 边界：$n=2$ 时唯一方案 $j=1,i=2$；$d_i=0$ 时 $pos$ 非严格递增，仍满足查询单调；答案可达 $10^{10}$ 量级，需要 64 位整数（Python 天然支持）。

图示解析

把全文推导压缩成一条路线，方便读完后复盘：

flowchart TD
    A["方案归一化：<br/>新厂只考虑建在树位置，<br/>方案 = 三段连续的树"] --> B["朴素 DP：<br/>f[i] = min_j (C1(j) + C2(j,i))<br/>O(n^2)，瓶颈在枚举 j"]
    B --> C["前缀和展开：<br/>f[i] = sw[i]·pos_i - swd[i]<br/>+ min_j ( -sw[j]·pos_i + sw[j]·pos_j )"]
    C --> D["决策 j 变成一条直线：<br/>斜率 m_j = -sw[j]，截距 b_j = sw[j]·pos_j"]
    D --> E["两个单调性：<br/>斜率严格递减（w≥1）<br/>查询点 pos_i 不减（d≥0）"]
    E --> F["查询：队头指针只前进<br/>均摊 O(1)"]
    E --> G["插入：队尾交叉相乘弹线<br/>均摊 O(1)"]
    F --> H["ans = min_i (f[i] + 尾段 C3(i))<br/>总复杂度 O(n)"]
    G --> H

上半部分是建模与化简：先确定方案的三段形状，再用前缀和把转移拆成「只与 $i$ 有关」加「直线族在 $pos_i$ 处取最小」。下半部分是数据结构依据：双单调性让插入与查询都只移动指针，最终把 $O(n^2)$ 降到 $O(n)$。