形式化题目

给定长度 $N$ 的任务序列，第 $i$ 个任务需要机时 $T_i$、费用系数 $C_i$，另有常数 $S$（启动时间）。要求把下标 $1 \ldots N$ 划分成若干连续段（批）：

1. 每批开工前机器先耗时 $S$，再依次执行批内任务；
2. 同一批任务在该批最后一个任务结束的时刻同时完成；
3. 任务 $i$ 的费用 $=$ 它的完成时刻 $\times C_i$，总费用 $=$ 所有任务费用之和。

求总费用的最小值。

记前缀和 $\mathrm{sumT}[i] = \sum_{k \leqslant i} T_k$、$\mathrm{sumC}[i] = \sum_{k \leqslant i} C_k$（下标 0 处取 0）。若划分的批尾依次为 $e_1 < \cdots < e_K = N$（$e_0 = 0$），批 $m$ 覆盖 $(e_{m-1}, e_m]$，则

完成时刻里的批数 $m$ 由划分本身决定、只看前缀时未知——这是全题的难点所在。

样例 $N = 5,\ S = 1$、$(T_i, C_i) = (1,3),\ (3,2),\ (4,3),\ (2,3),\ (1,4)$ 的一种最优划分是 $\{1,2\},\ \{3,4\},\ \{5\}$，逐批计算如下：

总费用 $25 + 72 + 56 = 153$，与输出一致。注意完成时刻随批数累进：批 3 的完成时刻是 $11 + 3$ 而不是 $11 + 1$——每多分一批，其后所有任务都被推迟一个 $S$；若五项并成一批则费用为 $12 \times 15 = 180$，正说明分批方案确实影响总费用，且最优划分不唯一（$\{1,2\},\{3\},\{4,5\}$ 也是 $153$）。

正解

思路

朴素建模与瓶颈。 最直接的思路是枚举全部 $2^{N-1}$ 种划分；退一步把批数放进状态：设 $f[i][k]$ 为前 $i$ 个任务恰好分 $k$ 批的最小费用，转移

单层 $\min$ 扫描 $O(N)$，$k$ 最坏到 $N$，总复杂度 $O(N^2K) \approx O(N^3)$；即便每层换成斜率优化也只降到 $O(N^2)$，对 $N = 3 \times 10^5$ 都不可行。瓶颈不在 $\min$ 扫描本身，而在完成时刻里的批数 $m$：它让状态无法只用前缀表示。

关键一步：给启动费换个记账口径，批数就消失了。 原式里批 $m$ 的启动费贡献是 $m \cdot S \cdot \Delta C_m$（记 $\Delta C_m = \mathrm{sumC}[e_m] - \mathrm{sumC}[e_{m-1}]$ 为批内费用系数之和）。换个角度看：批 $m$ 开始的那次 $S$ 会把"从这批第一个任务到最后一个任务 $N$"整体推迟 $S$，于是同一笔费用也可以记成 $S \cdot (\mathrm{sumC}[N] - \mathrm{sumC}[e_{m-1}])$——只与批的起点有关。两种记法相等：

第一个等号是分部求和：展开 $\sum_m m\big(\mathrm{sumC}[e_m] - \mathrm{sumC}[e_{m-1}]\big)$ 后把 $\mathrm{sumC}[e_m]$ 重新配对，中间项相邻相消，只剩末批的 $K\,\mathrm{sumC}[e_K]$ 减去各中间批尾的前缀和；第二个等号只是把 $K$ 个 $\mathrm{sumC}[N]$ 按批起点逐项分摊，用到 $e_0 = 0$（$\mathrm{sumC}[0] = 0$）与 $e_K = N$，即首批从 1 开始、末批铺到 $N$。记账口径下费用按批可加、每批只依赖起点 $j$ 和终点 $i$，于是得到只依赖前缀的 $O(N^2)$ DP：

答案是 $f[N]$。

$f[i]\ (i < N)$ 并不是前 $i$ 个任务的真实费用：它把启动费按"到 $N$ 为止"预记了出去，只有 $f[N]$ 恰好等于真实答案。正确性靠两点：全局口径 $\mathrm{sumC}[N]$ 在所有批上一致，因此记账值与真实值在完整划分上相等；记账费用对批次可加，前缀最优子结构成立。

展开成直线族。 把转移里只含 $j$ 的项收进直线参数、只含 $i$ 的项提到 $\min$ 外：

即每个前缀 $j$ 对应一条直线 $y = m_j x + b_j$，查询点是 $x_i = \mathrm{sumT}[i] + S$。由 $C_i \geqslant 0$ 知 $\mathrm{sumC}[j]$ 不减，斜率 $m_j$ 单调不增——直线按序加入，维护下凸壳即可；而 $T_i$ 可负使查询点 $x_i$ 不单调，所以查询必须二分（单调队列 $O(1)$ 摊还版在这里不成立）。插入均摊 $O(1)$、查询 $O(\log N)$，总复杂度 $O(N \log N)$。

维护细节三条：同斜率（$C_i = 0$ 使 $\mathrm{sumC}$ 不变）只留截距小的；加入新直线时若交点不再严格递增，中间那条在任何 $x$ 处都轮不到，删之；交点一律存成分数并用交叉相乘比较——$f$ 量级达 $10^{16}$，float 的 53 位尾数在该量级误差可超过 1，会把 DP 引向错误转移。

样例上的 DP 追踪。 下表逐行给出查询点、直线族在该点的取值 $f[j] - \mathrm{sumC}[j] \cdot x_i$、最小值来源与结果（前置项 $= \mathrm{sumT}[i]\,\mathrm{sumC}[i] + 15$）：

观察三点：$j = 0$ 的水平直线（斜率 0）代表"整段并成一批"的候选，每行都参与比较；每行 $f[i]$ 的胜负完全由 $\min$ 那一列决定，前置项只是统一抬高；最终 $153 = 180 + (-27)$，回溯决策 $j = 4 \to 2 \to 0$，恰好还原样例表中的 $\{1,2\},\{3,4\},\{5\}$（$j = 3$ 同为 $-27$，对应并列最优划分 $\{1,2\},\{3\},\{4,5\}$）。

代码

与正文符号的对应：setup 即 $S$，sum_t / sum_c 是前缀和，tail_c 即记账口径的 $\mathrm{sumC}[N]$；crossing 求两直线交点分数 $(n, d)$（$d > 0$），hull_push 做"同斜率取舍 + 尾部删除 + 追加交点"的插入维护，hull_min 在交点上二分查询；ms / bs / thr 三个平行列表即凸壳的斜率、截距、交点阈值。主循环先查询后插入（$j < i$ 严格更小），$j = 0$ 的直线 $(0, 0)$ 循环前预置，最后的 f 即 $f[N]$。读入用 re.findall 直接从输入中抽数字序列，对分隔符不敏感（本地真实数据有一处换行损坏成控制字节，逐行 split() 会失败）。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88#!/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:49
# update_at: 2026-09-30 21:49

import re
import sys
from itertools import accumulate

# 01~06 过程见 problem-analysis-workspace/；核心推导：
# 把每批启动费 S 改记为"批次开始时对之后所有任务的费用系数付费"（S*(总C - 前缀C_j)），
# 交叉项只剩 -sum_t[i]*sum_c[j]，DP 变成在直线族 y = -sum_c[j]*x + f[j] 上、
# 取 x = sum_t[i] + S 处的最小值 —— 斜率随 j 单调不增，可维护下凸壳。


def crossing(left: tuple[int, int], right: tuple[int, int]) -> tuple[int, int]:
    """两条直线交点的分数 (分子, 分母)，分母 > 0；交点右侧斜率小的那条更优。"""
    (m1, b1), (m2, b2) = left, right
    return b2 - b1, m1 - m2


def hull_push(ms: list[int], bs: list[int], thr: list[tuple[int, int]], m: int, b: int) -> None:
    """斜率单调不增地插入直线 y = m*x + b，删掉尾部从此取不到最小值的直线。"""
    while ms and m == ms[-1]:  # 同斜率只留截距小的，新直线处处不更优就直接丢弃
        if b >= bs[-1]:
            return
        ms.pop()
        bs.pop()
        if thr:
            thr.pop()

    # 交点必须严格递增，否则夹在中间的直线在任何 x 处都轮不到
    while len(ms) >= 2:
        n1, d1 = crossing((ms[-2], bs[-2]), (ms[-1], bs[-1]))
        n2, d2 = crossing((ms[-1], bs[-1]), (m, b))
        if n1 * d2 < n2 * d1:  # 分数比较：交点左移说明中间直线是废的
            break
        ms.pop()
        bs.pop()
        thr.pop()

    if ms:
        thr.append(crossing((ms[-1], bs[-1]), (m, b)))
    ms.append(m)
    bs.append(b)


def hull_min(ms: list[int], bs: list[int], thr: list[tuple[int, int]], x: int) -> int:
    """在下凸壳上二分：找到第一条 x 尚未越过其交点的直线，返回它在 x 处的值。"""
    lo, hi = 0, len(thr)
    while lo < hi:
        mid = (lo + hi) >> 1
        num, den = thr[mid]
        if x * den > num:  # x 已经越过交点，右边的直线更优
            lo = mid + 1
        else:
            hi = mid
    # lo 越过全部交点时正好等于最后一段直线的下标（len(thr) == len(ms) - 1）
    return ms[lo] * x + bs[lo]


def solve() -> None:
    nums = list(map(int, re.findall(rb'-?\d+', sys.stdin.buffer.read())))
    n, setup = nums[0], nums[1]
    ts = nums[2::2][:n]
    cs = nums[3::2][:n]

    sum_t = list(accumulate(ts, initial=0))  # 任务用时前缀和
    sum_c = list(accumulate(cs, initial=0))  # 费用系数前缀和，同时充当直线斜率
    tail_c = sum_c[-1]

    ms = [0]  # 直线族先放 j = 0：斜率 -sum_c[0] = 0
    bs = [0]  # 截距 f[0] = 0
    thr: list[tuple[int, int]] = []
    f = 0

    for i in range(1, n + 1):
        x = sum_t[i] + setup  # 查询点：前缀用时 + 启动费
        f = sum_t[i] * sum_c[i] + setup * tail_c + hull_min(ms, bs, thr, x)
        hull_push(ms, bs, thr, -sum_c[i], f)

    print(f)


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/**
 * 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:30
 * update_at: 2026-10-05 12:30
 */
// main.cpp：任务安排 3，把启动费改记为「批开始时对之后所有任务的费用系数付费」，
// 消掉完成时刻里的批数，DP 化为直线族 y = -sum_c[j]*x + f[j] 在 x = sum_t[i] + S 处的最小值查询。
// 斜率 -sum_c[j] 单调不增，维护下凸壳；查询点 x 不单调（T_i 可负），故在交点上二分，总复杂度 O(N log N)。
#include <cstdio>

typedef long long ll;
typedef __int128 wide; // 只用于交点比较时的交叉相乘，乘积可达 1e24，超出 ll

const int MAXN = 300005;

ll n;            // 任务个数
ll setup;        // 每批的启动时间 S
ll sum_t[MAXN];  // sum_t[i]：前 i 个任务的用时前缀和
ll sum_c[MAXN];  // sum_c[i]：前 i 个任务的费用系数前缀和，同时充当直线斜率

// 下凸壳：直线 y = hull_m[k]*x + hull_b[k]，斜率严格递减
ll hull_m[MAXN];   // hull_m[k] = -sum_c[j]，随 j 单调不增
ll hull_b[MAXN];   // hull_b[k] = f[j]（记账口径的 DP 值）
ll cut_num[MAXN];  // cut_num[k]/cut_den[k]：第 k 与第 k+1 条直线的交点横坐标
ll cut_den[MAXN];  // 交点分母恒为正（相邻两条直线前一条斜率更大）
int hull_size = 0; // 凸壳上的直线条数

// 快速读入一个整数：跳过所有非数字、非负号的字符，
// 这样即使分隔符里混有损坏的控制字符也能正确读完（本地数据出现过这种情况）。
ll read_int() {
    int ch = getchar();
    while (ch != EOF && ch != '-' && (ch < '0' || ch > '9')) {
        ch = getchar();
    }
    ll sign = 1;
    if (ch == '-') {
        sign = -1;
        ch = getchar();
    }
    ll value = 0;
    while (ch >= '0' && ch <= '9') {
        value = value * 10 + (ch - '0');
        ch = getchar();
    }
    return sign * value;
}

// 往凸壳里插入直线 y = m*x + b，斜率保持不增，删掉以后取不到最小值的直线
void hull_push(ll m, ll b) {
    // 同斜率只留截距小的；新直线处处不更优就直接丢弃
    while (hull_size > 0 && m == hull_m[hull_size - 1]) {
        if (b >= hull_b[hull_size - 1]) {
            return;
        }
        hull_size--;
    }
    // 相邻交点必须严格递增，否则夹在中间的那条直线在任何 x 处都轮不到
    while (hull_size >= 2) {
        ll n1 = hull_b[hull_size - 1] - hull_b[hull_size - 2];
        ll d1 = hull_m[hull_size - 2] - hull_m[hull_size - 1];
        ll n2 = b - hull_b[hull_size - 1];
        ll d2 = hull_m[hull_size - 1] - m;
        if ((wide)n1 * d2 < (wide)n2 * d1) { // 分数比较：交点左移说明中间直线是废的
            break;
        }
        hull_size--;
    }
    if (hull_size > 0) {
        cut_num[hull_size - 1] = b - hull_b[hull_size - 1];
        cut_den[hull_size - 1] = hull_m[hull_size - 1] - m;
    }
    hull_m[hull_size] = m;
    hull_b[hull_size] = b;
    hull_size++;
}

// 在下凸壳上二分：找到第一条查询点尚未越过其左端交点的直线，返回它在 x 处的值
ll hull_min(ll x) {
    int left = 0;
    int right = hull_size - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if ((wide)x * cut_den[mid] > cut_num[mid]) { // x 已越过交点，右侧直线更优
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return hull_m[left] * x + hull_b[left];
}

int main() {
    n = read_int();
    setup = read_int();
    for (int i = 1; i <= n; i++) {
        ll t = read_int();
        ll c = read_int();
        sum_t[i] = sum_t[i - 1] + t;
        sum_c[i] = sum_c[i - 1] + c;
    }
    ll tail_c = sum_c[n]; // 记账口径里所有批共用的总费用系数

    hull_push(0, 0); // 预置 j = 0 的直线：斜率 -sum_c[0] = 0，截距 f[0] = 0
    ll f = 0;
    for (int i = 1; i <= n; i++) {
        ll x = sum_t[i] + setup; // 查询点
        f = sum_t[i] * sum_c[i] + setup * tail_c + hull_min(x);
        hull_push(-sum_c[i], f); // 先查询后插入，保证转移来源 j < i
    }
    printf("%lld\n", f);
    return 0;
}

复杂度

• 时间复杂度：$O(N \log N)$——$N$ 次查询各二分 $O(\log N)$，插入均摊 $O(1)$（每条直线至多入壳、出壳各一次）；与标准 C++ 正解（单调斜率 + 任意序查询的凸壳 / 李超线段树）同阶。$N = 3 \times 10^5$ 时约 $3 \times 10^5 \times 19$ 次比较量级。
• 空间复杂度：$O(N)$——前缀和与凸壳三平行列表各 $\leqslant N + 1$；实测 $N = 3 \times 10^5$ 峰值约 61 MB，对照 128 MB 宽裕。
• 实测：真实数据 20 组全部一致，$N = 3 \times 10^5$ 单点 0.53–0.57 s、$N = 10^5$ 约 0.14 s（本地宽松时限）；对照 OJ 1000 ms 限制，内存无压力、时间在更慢的 OJ 机器上存在可接受的 TLE 风险（按 python-oj-short 约定允许）。

总结

本题的难点是完成时刻里的批数 $m$：直接把批数放进状态会退化到 $O(N^2K)$。换记账口径——启动费 $S$ 在批开始时支付、按"从该批起点到末尾所有任务"的费用系数计费（分部求和保证与原式相等）——批数被消掉，得到只依赖前缀的 $O(N^2)$ DP；再把转移按 $j$ 展开成直线族，$C_i \geqslant 0$ 保证斜率单调不增，下凸壳二分把总复杂度压到 $O(N \log N)$。易错点有四：$f[i]$ 是记账口径、只有 $f[N]$ 是答案；$C_i = 0$ 的同斜率直线必须只留截距小者；$T_i$ 可负使查询点不单调（也使答案可能为负，如真实数据中的负输出），不能用 $O(1)$ 摊还版；交点比较必须用整数分数交叉相乘，不能用浮点。实测真实数据 20/20 全部一致，最大 $N = 3 \times 10^5$ 单点 0.53–0.57 s、峰值 61 MB。