「一本通 5.6 例 2」任务安排 2

形式化题目

$N$ 个任务顺序不变地分成若干连续批次执行。每批的执行时间为启动时间 $S$ 加批内各任务耗时 $T_i$ 之和；同批任务同时完成，任务 $i$ 的费用为完成时刻乘费用系数 $C_i$ 。求总费用最小的分批方案。

正解

思路

1. 基础 DP

设 $f[i]$ 为前 $i$ 个任务分批的最小总费用，枚举最后一批的起点 $j$ （第 $j+1 \dots i$ 个任务为一批）：

f[i] = \min_{0 \le j < i} \left\{ f[j] + \left(S + \sum_{t=j+1}^{i} T_t\right) \times \sum_{t=j+1}^{i} C_t \right\}

直接枚举是 $O(n^2)$ ，对 $n = 3 \times 10^5$ 超时。

2. 换记账次序展开转移

记前缀和 $pre_t[i] = \sum_{t \le i} T_t$ 、 $pre_c[i] = \sum_{t \le i} C_i$ 。一个经典技巧：提前计算启动时间对后面所有任务的费用贡献——把 $S$ 视为影响此后全部任务，转移改写为：

f[i] = \min_j \left\{ f[j] + (S + pre_t[i] - pre_t[j]) \times (pre_c[i] - pre_c[j]) \right\}

展开并把只与 $j$ 有关的量合并（关键的代数变形，使 $i, j$ 解耦为"斜率 × 横坐标 + 截距"）：

f[i] = pre_t[i] \times pre_c[i] + \min_j \left\{ y[j] - pre_t[i] \times pre_c[j] \right\}

其中 $y[j] = f[j] - pre_t[j] \times (pre_c[i] - pre_c[j]) + S \times (pre_c[i] - pre_c[j])$ 在实现里按等价形式逐项递推计算。

3. 斜率优化 + 单调队列

上式即：用斜率 $k = pre_t[i]$ 的直线去切决策点集 $\{(pre_c[j], y[j])\}$ 的下凸壳，取截距最小者。两个单调性使整个过程 $O(n)$ ：

查询斜率单调： $T_i > 0 \Rightarrow pre_t[i]$ 严格递增，队头最优性一旦被超越就永久失效，popleft 弹出；
插入横坐标单调： $C_i > 0 \Rightarrow pre_c[j]$ 严格递增，新点只需在队尾弹出破坏凸性的旧点。

凸性比较用叉积（乘法交叉相乘）代替斜率除法，避免浮点误差。每个决策入队出队各一次，总复杂度线性。

代码

Python 版：

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#!/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:50
# update_at: 2026-09-30 21:50

import sys
from collections import deque
from itertools import accumulate


def min_cost(startup: int, pre_t: list[int], pre_c: list[int]) -> int:
    """前 n 个任务分批的最小总费用 f[n]（斜率优化，O(n)）。

    换记账次序后 f[i] = min_j { f[j] + (startup + pre_t[i]-pre_t[j]) × (pre_c[n]-pre_c[j]) }，
    把与 j 有关的量收成点 (pre_c[j], y[j])、与 i 有关的收成斜率 k = pre_t[i]，
    转移变成"用斜率 k 的直线去切下凸壳"，取 f[i] = k×pre_c[n] + min_j { y[j] - k×pre_c[j] }。
    T_i, C_i 均为正，pre_t 与 pre_c 严格递增，故查询斜率与插入横坐标都单调：
    队头弹出比不过的决策、队尾弹出破坏凸性的决策，每个决策进出队各一次。
    """
    n = len(pre_t) - 1
    total_c = pre_c[n]
    f = [0] * (n + 1)
    y = [0] * (n + 1)
    y[0] = startup * total_c  # j = 0 处的截距：f[0] - pre_t[0]×(total_c-pre_c[0]) + startup×total_c

    hull = deque([0])  # 下凸壳上决策点的编号，pre_c[j] 随入队单调递增
    for i in range(1, n + 1):
        k = pre_t[i]  # 本轮查询斜率，随 i 单调递增
        while len(hull) >= 2 and y[hull[0]] - k * pre_c[hull[0]] >= y[hull[1]] - k * pre_c[hull[1]]:
            hull.popleft()  # 队头不如次队头，且后面的 k 只会更大，此后再也用不到
        j = hull[0]  # 最优切点：使 f[i] 最小的那一段左边界
        f[i] = k * total_c + y[j] - k * pre_c[j]
        y[i] = f[i] - pre_t[i] * (total_c - pre_c[i]) + startup * (total_c - pre_c[i])
        while len(hull) >= 2:
            a, b = hull[-2], hull[-1]
            slope_ab = (y[b] - y[a]) * (pre_c[i] - pre_c[b])   # 叉积比较代替除法，避免精度
            slope_bi = (y[i] - y[b]) * (pre_c[b] - pre_c[a])
            if slope_ab >= slope_bi:
                hull.pop()  # b 被线段 a-i 盖住，不再在凸壳上
            else:
                break
        hull.append(i)
    return f[n]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)       # 任务数 n
    startup = next(data)  # 每批启动时间 S
    pairs = [(next(data), next(data)) for _ in range(n)]  # (T_i, C_i)，共 n 对
    times = [t for t, _ in pairs]
    fees = [c for _, c in pairs]
    pre_t = list(accumulate(times, initial=0))  # n+1 个前缀和，下标 0 处为 0
    pre_c = list(accumulate(fees, initial=0))
    print(min_cost(startup, pre_t, pre_c))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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// main.cpp：任务安排 2，斜率优化 DP 标准模板（单调队列维护下凸壳，O(n)）。

/**
 * 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 10:41
 * update_at: 2026-10-05 10:41
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 1e4 + 5;

ll n;              // 任务数
ll s;              // 每批的启动时间
ll t[MAXN], c[MAXN];   // t[i] 第 i 个任务耗时，c[i] 第 i 个任务费用系数
ll pret[MAXN], prec[MAXN]; // pret/prec：耗时与费用系数的前缀和，下标 0 处为 0
ll f[MAXN];        // f[i]：前 i 个任务分批的最小总费用
ll y[MAXN];        // y[j]：决策点 j 的纵坐标（见下方转移说明）
int q[MAXN];       // 单调队列：保存下凸壳上决策点的编号
int head, tail;    // 队头、队尾（左闭右开 [head, tail)）

// 判断队头决策是否已被次队头完全超越：用纵坐标差与横坐标差的叉积代替斜率除法。
// a、b 是队头前两个决策点，k 是本轮查询斜率 pret[i]。
bool head_worse(int a, int b, ll k) {
    return y[b] - k * prec[b] <= y[a] - k * prec[a];
}

// 判断新点 i 加入后，队尾决策点 b 是否被线段 a-i 盖住（破坏下凸性）。
bool tail_bad(int a, int b, int i) {
    return (y[b] - y[a]) * (prec[i] - prec[b]) >= (y[i] - y[b]) * (prec[b] - prec[a]);
}

int main() {
    scanf("%lld", &n);
    scanf("%lld", &s);
    for (int i = 1; i <= (int)n; i++) {
        scanf("%lld %lld", &t[i], &c[i]);
        pret[i] = pret[i - 1] + t[i];
        prec[i] = prec[i - 1] + c[i];
    }

    // 换记账次序：把启动时间 S 提前算进后续所有任务的费用，
    // 转移化为 f[i] = pret[i]*prec[n] + min_j { y[j] - pret[i]*prec[j] }，
    // 即用斜率 k = pret[i] 的直线去切决策点集 {(prec[j], y[j])} 的下凸壳。
    ll total_c = prec[n];
    f[0] = 0;
    y[0] = s * total_c; // j = 0 的纵坐标：f[0] - pret[0]*(total_c-prec[0]) + s*(total_c-prec[0])
    head = 0;
    tail = 0;
    q[tail++] = 0; // 初始决策点 j = 0 入队

    for (int i = 1; i <= (int)n; i++) {
        ll k = pret[i]; // 本轮查询斜率，因 T_i > 0 随 i 单调递增
        // 队头不再最优：因 k 单调增，被超越后永远用不到，直接弹出
        while (head + 1 < tail && head_worse(q[head], q[head + 1], k))
            head++;
        int j = q[head];
        f[i] = k * total_c + y[j] - k * prec[j];
        // 新决策点 i 的纵坐标（f[i] 代入换记账次序的展开式）
        y[i] = f[i] - pret[i] * (total_c - prec[i]) + s * (total_c - prec[i]);
        // 新点横坐标 prec[i] 单调递增，只需从队尾弹出破坏凸性的旧点
        while (head + 1 < tail && tail_bad(q[tail - 2], q[tail - 1], i))
            tail--;
        q[tail++] = i;
    }

    printf("%lld\n", f[n]);
    return 0;
}

复杂度

时间复杂度： $O(n)$ ，每个决策点最多入队、出队各一次，查询与维护均摊 $O(1)$ 。
空间复杂度： $O(n)$ ，前缀和数组、DP 数组与单调队列。

总结

任务安排 2 是斜率优化 DP 的标准模板题：核心是把转移展开整理成「斜率 × 横坐标 + 截距」的直线切凸壳形式。
换记账次序（启动费提前摊给后续任务）是让转移可分离的关键变形。
查询斜率与插入横坐标双单调 + 叉积判凸，把 $O(n^2)$ 压到 $O(n)$ 。