形式化题目

一条路旁有 $N$ 座山，第 $i-1$ 座到第 $i$ 座山的距离为 $D_i$。记 $s[h]$ 为从 1 号山走到 $h$ 号山的时间：$s[1]=0$，$s[h]=\sum_{i=2}^{h} D_i$。$M$ 只猫中第 $i$ 只在 $H_i$ 号山玩到时刻 $T_i$，之后原地等待。$P$ 位饲养员都住在 1 号山，各自选择一个出发时刻（可为负），以速度 1 沿路从 1 号山走到 $N$ 号山，把路上已经在等待的猫全部接走（接猫不耗时，载量无限）。求一种出发时刻安排，使所有猫的等待时间之和最小。

猫能否被某位饲养员接走，只取决于他的出发时刻 $t$：他到达 $H_i$ 号山的时刻是 $t + s[H_i]$，若 $t + s[H_i] < T_i$，他经过时猫还在玩，这只猫只能等后面的饲养员。于是每只猫可以压成一个数：

$a_i$ 就是能接到这只猫的出发时刻下限：饲养员不早于 $a_i$ 出发才接得到它，接走时这只猫已经等待了 $t - a_i$。

样例 $D=[1,3,5]$（即 $s=[0,1,4,9]$）、$P=2$，把六只猫按 $a_i$ 升序排好后，最优方案如下表——总等待 $0+0+0+2+1+0 = 3$，即样例输出：

注意两点：甲 $t=0$ 恰好不早于三只 $a=0$ 猫的下限，而他先于乙经过每座山，这三只归甲且等待为 $0$；乙的出发时刻被段尾 $a=10$ 顶住，后三只的等待 $2+1+0$ 就是这个方案里唯一的代价。若只有一位饲养员（$t=10$），前三只每只都要等 $10$，总和 $33$。

正解

思路

第一步：排序后，每位饲养员接走一段连续的猫。 饲养员走完全程，凡是 $a_i \leqslant t$ 的未接猫都会被他顺手接走——他无法跳过任何一座山，也就无法"挑猫"。把猫按 $a_i$ 升序排列、饲养员按出发时刻升序编号：第一位接走所有 $a \leqslant t_1$ 的猫，第二位接走 $(t_1, t_2]$ 的……因此第 $j$ 位饲养员恰好对应排序后的一个连续段，且后一位的出发时刻不早于前一位；反过来，任意连续段划分配上合法出发时刻都是可行方案。问题从"安排 $P$ 个时刻"变成了"把有序序列切成至多 $P$ 段"。

第二步：每段的最优出发时刻是段尾的 $a$。 段 $(k, r]$（第 $k{+}1 \ldots r$ 只猫）要求 $t \geqslant a_r$（段内最大的 $a$），等待和为

其中 $S_r = \sum_{i \leqslant r} a_i$ 是 $a$ 的前缀和（$S_0 = 0$）。这是 $t$ 的增函数，所以取 $t = a_r$，段费用 = $(r-k)\,a_r - (S_r - S_k)$，$O(1)$ 可算。

第三步：分段 DP 与瓶颈。 设 $f_p[r]$ = 前 $r$ 只猫用 $p$ 位饲养员的最小等待和：

$k = r$ 表示第 $p$ 位饲养员空跑（费用 0），所以 $f_p \leqslant f_{p-1}$ 逐点成立，少用饲养员总是合法；初始化 $f_0[0] = 0$，$f_0[r>0] = +\infty$（0 位饲养员一只猫也接不到），答案是 $f_P[M]$。朴素实现对每个 $(p, r)$ 扫一遍 $k$，共 $O(PM^2)$ 次转移，$M = 10^5$ 时约 $10^{12}$ 次，完全不可行；而 $P \leqslant 100$ 让 $O(PM)$ 成为唯一可行的量级——瓶颈只剩"每个 $r$ 都要把 $k$ 全扫一遍"。

第四步：把转移整理成直线族。 把只与 $r$ 有关的项提出 min：

每个切点 $k$ 对应一条直线 $\ell_k:\ y = m_k x + b_k$（斜率 $m_k = -k$、截距 $b_k = f_{p-1}[k] + S_k$），查询点是 $x = a_r$，DP 变成"在直线族上查询 $x = a_r$ 处的最小值"。且双单调性天然成立：

• 斜率单调：插入顺序 $k = 0,1,2,\ldots$，斜率 $-k$ 严格递减；
• 查询单调：$r$ 递增时查询点 $x = a_r$ 非降（已排序）。

斜率单调、查询单调 ⇒ 用双端队列维护直线族的下凸壳：查询时若 value(front) >= value(second) 就弹队首（首线被追平后对更大的 $x$ 只会更差）；插线时若新线与队尾线的交点 $x_{12}$ 不晚于队尾与前一条的交点 $x_{23}$，则队尾线的生效区间为空，弹队尾——交点比较的分母同号，交叉相乘即可用整数精确判断。每条直线进出队列各一次，单层均摊 $O(1)$。

样例的两层 DP。 下表按 $r$ 列出转移结果：$f_1$ 只有一位饲养员（$k=0$ 是唯一可达切点），$f_2$ 是两位饲养员，末列是 $f_2$ 取到最小值的切点 $k$。

表中能读出三件事：一人全接（$t = 10$）要等 $33$；第二层在 $k = 3$ 处切开后，前三只猫归甲（等待 0），$f_2$ 从 $r=4$ 起骤降；最优 $k$ 随 $r$ 单调右移到 3 后停住——这正是"查询时弹队首"所依赖的单调事实。验证 $r=6$（$x = 10$）：第二层直线取值 $\ell_0 = 0$、$\ell_3 = 0 - 3\times10 = -30$、$\ell_4 = 32 - 40 = -8$，最小 $-30$，故 $f_2[6] = 6\times10 - 27 - 30 = 3$，即样例答案。

代码

下面的 dp_layer() 就是上述单调队列：dq 存直线 $(m, b) = (-k,\ f_{p-1}[k]+S_k)$，队尾 while 用交叉相乘判死线，查询 while 弹队首，f[r] = r*x - pre[r] + 最优直线取值 即第四步整理出的三段；循环里先插 $k=r$ 再查 $x=a_r$，保证查询时 $k=0..r$ 全在壳内（$k=r$ 的空段项不丢），而插入序与查询序的单调性不受影响。solve() 负责读入、算 $a_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
67
68
69#!/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:45
# update_at: 2026-09-30 21:45

import sys
from collections import deque
from itertools import accumulate

INF = 10**30  # 不可达 DP 值的哨兵，远大于任何合法答案


def dp_layer(prev: list[int], limit: list[int], pre: list[int]) -> list[int]:
    """多用一只饲养员推进一层 DP：f[r] = min_k prev[k] + (r-k)*a_r - (pre[r]-pre[k])。

    猫按 a 升序排好后，每只饲养员接走的必是一段连续的猫，段 (k, r] 的最优出发时刻
    就是段尾 a_r；把转移整理成 f[r] = r*a_r - pre[r] + min_k {(prev[k]+pre[k]) - k*a_r}，
    每个 k 就是一条斜率 -k、截距 prev[k]+pre[k] 的直线。加入序斜率递减、查询点
    a_r 递增（非降），用单调队列维护下凸壳，摊还每步 O(1)。
    """
    dq: deque[tuple[int, int]] = deque()  # (斜率, 截距)，斜率自队头向队尾递减
    n = len(limit)
    f = [INF] * (n + 1)
    for r in range(n + 1):
        if prev[r] < INF:  # 不可达的切点 k 不入壳
            m, b = -r, prev[r] + pre[r]
            # 队尾直线的生效区间被新交点截空（x12 <= x23）→ 它永远取不到最小值
            while len(dq) >= 2 and (b - dq[-1][1]) * (dq[-2][0] - dq[-1][0]) <= (dq[-1][1] - dq[-2][1]) * (dq[-1][0] - m):
                dq.pop()
            dq.append((m, b))
        if r == 0:
            f[0] = 0  # 0 只猫的费用恒为 0，它也是下一层 k=0 的直线来源
            continue
        x = limit[r - 1]  # a_r：段尾猫要求饲养员不早于它出发
        # 查询点递增，队头若已不如第二条就出队
        while len(dq) >= 2 and dq[0][0] * x + dq[0][1] >= dq[1][0] * x + dq[1][1]:
            dq.popleft()
        f[r] = r * x - pre[r] + dq[0][0] * x + dq[0][1]
    return f


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

    # 前缀距离：reach[h] = 1 号山走到 h 号山需要的时间
    reach = [0] * (N + 1)
    for h in range(2, N + 1):
        reach[h] = reach[h - 1] + next(data)

    # 每只猫只依赖 a = T - s[H]：饲养员出发不早于 a 才接得到，等待 = 出发时刻 - a
    cats = [(next(data), next(data)) for _ in range(M)]  # (H, T)，题面顺序
    limit = sorted(t - reach[h] for h, t in cats)  # a_1..a_M 升序
    pre = list(accumulate(limit, initial=0))  # a 的前缀和，pre[r] = sum_{i<=r} a_i

    prev = [INF] * (M + 1)
    prev[0] = 0  # 0 只饲养员一只猫也接不到
    for _ in range(P):
        cur = dp_layer(prev, limit, pre)
        if cur == prev:  # 已到不动点：再加饲养员结果也不会变
            break
        prev = cur
    print(prev[M])


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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116/**
 * 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:31
 * update_at: 2026-10-05 12:31
 */
// 斜率优化 DP：猫压成 a = T - s[H] 后排序，P 位饲养员各接一段连续的猫，
// 转移整理成直线族（斜率 -k、截距 f[k]+S[k]），双单调用单调队列维护下凸壳。

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // 山和猫的数量上限
const ll INF = 4e18;     // 不可达 DP 值的哨兵

ll n, m, p;      // 山数、猫数、饲养员数
ll s[MAXN];      // s[h]：1 号山走到 h 号山的时间（距离前缀和）
ll a[MAXN];      // a[i]：第 i 只猫（排序后）能被接走的出发时刻下限
ll pre[MAXN];    // pre[i]：a 的前缀和
ll f[2][MAXN];   // 滚动数组：f[cur][r] = 前 r 只猫用当前位数饲养员的最小等待和

struct Cat {
    ll h;
    ll t;
};
Cat cats[MAXN]; // 每只猫所在山编号与玩到时刻

// 判断队尾直线 (m2,b2) 是否被新线 (m1,b1) 与队尾前一条线 (m3,b3) 夹死（生效区间为空）
// 即新线与队尾线的交点 x12 不晚于队尾线与前一条线的交点 x23，交叉相乘避免除法
bool bad_line(ll m1, ll b1, ll m2, ll b2, ll m3, ll b3) {
    // x12 <= x23，即 (b2-b1)*(m2-m3) <= (b3-b2)*(m1-m2)；
    // b 可达 2e14、斜率差可达 1e5，乘积可超 ll，用 __int128 承接
    __int128 lhs = b2 - b1;
    lhs *= m2 - m3;
    __int128 rhs = b3 - b2;
    rhs *= m1 - m2;
    return lhs <= rhs;
}

// 用上一层 DP 值 prevdp[] 推进一层：
// f[r] = min_k prevdp[k] + (r-k)*a_r - (pre[r]-pre[k])
// 把每个切点 k 看成直线 y = -k*x + (prevdp[k]+pre[k])，查询点 x = a_r
void dp_layer(ll *prevdp, ll *curdp) {
    // dq 存直线 (斜率, 截距)，斜率自队头向队尾递减（k 递增）
    deque<pair<ll, ll> > dq;
    for (ll r = 0; r <= m; r++) {
        if (prevdp[r] < INF) { // 不可达切点不入壳
            ll nm = -r, nb = prevdp[r] + pre[r];
            // 队尾直线的生效区间被新线截空则弹出（交点比较交叉相乘，整数精确）
            while (dq.size() >= 2 && bad_line(nm, nb, dq.back().first,
                   dq.back().second, dq[dq.size() - 2].first, dq[dq.size() - 2].second))
                dq.pop_back();
            dq.push_back(make_pair(nm, nb));
        }
        if (r == 0) {
            curdp[0] = 0; // 0 只猫费用恒为 0，也是下一层 k=0 的直线来源
            continue;
        }
        ll x = a[r]; // 查询点：段尾猫的出发时刻下限，随 r 非降
        // 查询点递增，队头若已不如第二条则永远不再最优，弹出
        while (dq.size() >= 2 && dq.front().first * x + dq.front().second >=
               dq[1].first * x + dq[1].second)
            dq.pop_front();
        curdp[r] = r * x - pre[r] + dq.front().first * x + dq.front().second;
    }
}

void read_input() {
    cin >> n >> m >> p;
    s[1] = 0;
    for (ll i = 2; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    for (ll i = 1; i <= m; i++) {
        cin >> cats[i].h >> cats[i].t;
    }
}

void solve() {
    // 每只猫压成 a = T - s[H]：饲养员不早于 a 出发才接得到，等待 = 出发时刻 - a
    for (ll i = 1; i <= m; i++) {
        a[i] = cats[i].t - s[cats[i].h];
    }
    sort(a + 1, a + m + 1);
    for (ll i = 1; i <= m; i++) {
        pre[i] = pre[i - 1] + a[i];
    }

    // 初始：0 位饲养员一只猫也接不到，只有 f[0]=0 可达
    for (ll r = 1; r <= m; r++) {
        f[0][r] = INF;
    }
    f[0][0] = 0;
    ll cur = 0; // 滚动数组当前层下标
    for (ll layer = 1; layer <= p; layer++) {
        dp_layer(f[cur], f[cur ^ 1]);
        cur ^= 1;
    }
    cout << f[cur][m] << "\n";
}

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

    read_input();
    solve();

    return 0;
}

复杂度

• 时间复杂度：前缀距离与前缀和 $O(N + M)$，排序 $O(M \log M)$，$P$ 层 DP 每层摊还 $O(M)$，共 $O(PM)$；$P \cdot M \leqslant 10^7$，与标准 C++ 斜率优化解法同阶。
• 空间复杂度：$O(N + M)$（前缀距离、$a$、前缀和、两层 DP 数组与队列），峰值约 70MB。
• 数值：答案可达 $10^{14}$，凸壳交点交叉相乘约 $10^{19}$，Python int 任意精度无溢出；实测最坏数据本地约 6.3s，对比 OJ 的 1000ms 时限 Python 侧存在 TLE 风险（按任务约定允许）。

总结

• 关键观察是把每只猫压成 $a_i = T_i - s[H_i]$：位置与玩到的时刻两个字段合并成"能接它的出发时刻下限"，等待时间 = 出发时刻 $- a_i$。
• 饲养员走完全程、无法挑猫 ⇒ 排序后每位饲养员接一段连续的猫，段费用前缀和 $O(1)$，问题变成至多 $P$ 段的区间划分 DP。
• 转移式对切点 $k$ 是一次函数，把"枚举切点"变成"直线上查询最小值"；斜率 $-k$ 递减、查询点 $a_r$ 非降，双单调性让下凸壳退化为双端队列，单层摊还 $O(1)$。
• 易错点：$f_p[0]=0$ 与 $k=r$ 的空段项不能丢（前者还是下一层首条直线的来源）；$a_i$ 可相等、可为负，只要查询点非降即可，交点比较必须用整数交叉相乘。

图示解析

下图是从输入到答案的完整推导链路，每一步只做一件事：

flowchart LR
  A["输入 D_i, H_i, T_i"] --> B["前缀距离 s[h]"]
  B --> C["压参 a = T - s[H]"]
  C --> D["按 a 升序排序 + 前缀和 S"]
  D --> E["P 层分段 DP<br/>f_p[r] = min_k ..."]
  E --> F["提出 r 相关项<br/>切点 k 变成直线 y = -k x + b"]
  F --> G["单调队列维护下凸壳<br/>查询 x = a_r"]
  G --> H["f_P[M] 即答案"]

观察重点：排序（C→D）是"谁接谁"从集合变成连续段的分水岭；直线的斜率来自切点下标 $k$、查询点来自段尾 $a_r$（E→F），两者的单调性同向，才让每层 DP 的插线与查询都只需摊还 $O(1)$（G）。