形式化题目

$N$ 个任务排成固定序列，顺序不可变，只能把它们切成若干段连续的批。每批开始前机器要付出固定启动时间 $S$，批的耗时 = $S$ + 批内各任务耗时之和；批内任务在该批全部执行完毕的同一时刻完成。任务 $i$ 的费用 = 它的完成时刻 $\times$ 费用系数 $C_i$，求所有任务的最小总费用。

形式化地：设划分点 $0 = b_0 < b_1 < \dots < b_k = N$，第 $r$ 批为 $(b_{r-1}, b_r]$，任务 $i$ 的完成时刻是它所在批及之前所有批的耗时之和，目标是 $\min \sum_{i=1}^{N} C_i \cdot \text{finish}(i)$。

样例的最优方案是 $\{1,2\},\{3\},\{4,5\}$：完成时刻 $\{5,5,10,14,14\}$，总费用 $5\times3+5\times2+10\times3+14\times3+14\times4 = 153$。

正解

思路

朴素想法与瓶颈。 最自然的 DP 是设 $f[i]$ = 前 $i$ 个任务的最小费用、枚举最后一段 $(j,i]$，但转移要用"前 $j$ 个任务跑完的时刻"，而它取决于前 $j$ 个任务怎么分批：同一个 $j$ 对应多种完成时刻，一个 $f[j]$ 数值记不下；把时刻并入状态又会维数爆炸。卡点在于每批的 $S$ 不只推迟本批任务，还推迟它后面所有批次任务的完成时刻——这是跨段的全局耦合，正着按"完成时刻"算就必须知道未来。

下图展示样例三条批的时间线，观察完成时刻如何逐批累加、前批的耗时被后批任务共享：

flowchart LR
  b1["批 1,2<br/>S+1+3 = 5"] --> b2["批 3<br/>S+4 = 5"] --> b3["批 4,5<br/>S+2+1 = 4"]
  f1["完成时刻 5"] -.-> b1
  f2["完成时刻 10"] -.-> b2
  f3["完成时刻 14"] -.-> b3

批 1 的 $5$ 同时出现在任务 3、4、5 的完成时刻里，正说明"一批的耗时会被它之后的所有任务共享"。

换一种记账方式。 把总费用按批分组（交换求和次序）：批 $b$ 的 $(S+\sum T)$ 出现在它自己及之后每一批的完成时刻中，被这些批里任务的 $C_i$ 各加一次，于是

批 $(j,i]$ 的贡献 = $(S + \text{该批时间和}) \times (j \text{ 之后所有任务的} C \text{ 之和})$，两项只依赖前缀和，$O(1)$ 可算。这样每批的账在切它时一次记清，"影响未来"的耦合随记账方式的改变消失了，DP 重新获得无后效性。

DP 定义。 用前缀和 $\mathrm{preT}[i]=\sum_{k\le i} T_k$、$\mathrm{preC}[i]=\sum_{k\le i} C_k$（下标 0 处为 0），$f[i]$ = 前 $i$ 个任务分批的最小总费用，$f[0]=0$：

下表是样例（$N=5,\ S=1$）的完整转移过程：行 = 右端点 $i$，列 = 枚举的切点 $j$，单元格 = 该切点的转移值，末列 $f[i]$ 取行内最小值。

注意 $j=0$ 表示"整个前缀一批打完"；$i=5$ 时 $j=3$ 对应样例方案 $\{1,2\},\{3\},\{4,5\}$，$j=4$ 对应 $\{1,2\},\{3,4\},\{5\}$，两者同为最优 153，说明多个划分可以共享同一最优值。最后一批之后没有任务，$\mathrm{preC}[N]-\mathrm{preC}[j]$ 恰是真实后缀，记账值等于真实费用，故 $f[N]$ 就是答案。

代码

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

import sys
from itertools import accumulate


def min_cost(startup: int, prefix_t: list[int], prefix_c: list[int]) -> int:
    """前 n 个任务分批的最小总费用 f[n]（f[0] = 0，O(n^2)）。

    同一批任务同时完成，所以批 (j, i] 的启动费 startup 会推迟它自己以及后面
    所有批次里任务的完成时刻；把总费用按批次交换求和次序，批 (j, i] 的贡献就是
    (startup + 该批时间和) × (j 之后所有任务的费用系数和)，前缀和让两项都是 O(1)。
    """
    total_c = prefix_c[-1]
    n = len(prefix_t) - 1
    f = [0] * (n + 1)  # f[i]：前 i 个任务分批的最小总费用
    for i in range(1, n + 1):
        time_i = prefix_t[i]
        f[i] = min(
            f[j] + (startup + time_i - prefix_t[j]) * (total_c - prefix_c[j])
            for j in range(i)
        )
    return f[n]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, startup = next(data), next(data)  # 任务数 n、每批启动时间 S
    tasks = [(next(data), next(data)) for _ in range(n)]  # 按题面结构成对消费：每个任务一行 (T_i, C_i)
    times = [t for t, _ in tasks]   # 各任务耗时 T_i，n 个
    fees = [c for _, c in tasks]    # 各任务费用系数 C_i，n 个
    prefix_t = list(accumulate(times, initial=0))   # n+1 个前缀和，下标 0 处为 0
    prefix_c = list(accumulate(fees, initial=0))
    print(min_cost(startup, prefix_t, prefix_c))


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/**
 * 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:23
 * update_at: 2026-10-05 12:23
 *
 * 「一本通 5.6 例 1」任务安排 1
 * 顺序不可变的序列切成连续若干批，每批开始前有固定启动时间 S。
 * 一批的耗时会被它之后所有任务共享，直接按“完成时刻”DP 会失去无后效性；
 * 交换求和次序后，批 (j, i] 的贡献 = (S + 该批耗时和) × (j 之后所有 C 之和)，
 * 两项都只依赖前缀和，于是 f[i] 只需枚举切点 j 即可转移：
 * f[i] = min_{j<i} f[j] + (S + preT[i] - preT[j]) * (preC[N] - preC[j])。
 * 时间复杂度 O(N^2)，空间 O(N)。
 */
#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXN = 5005;
const ll INF = 1000000000000000000LL; // 取最小值用的哨兵，远大于真实答案上界

ll n, S;
ll preT[MAXN]; // preT[i] = 前 i 个任务的耗时前缀和
ll preC[MAXN]; // preC[i] = 前 i 个任务的费用系数前缀和
ll f[MAXN];    // f[i] = 前 i 个任务分批的最小总费用（按批记账）

int main() {
    scanf("%lld %lld", &n, &S);
    for (ll i = 1; i <= n; i++) {
        ll t, c;
        scanf("%lld %lld", &t, &c);
        preT[i] = preT[i - 1] + t;
        preC[i] = preC[i - 1] + c;
    }

    ll totalC = preC[n]; // 全部任务的费用系数之和，用于取后缀和 preC[N] - preC[j]
    f[0] = 0;
    for (ll i = 1; i <= n; i++) {
        ll best = INF;
        // 枚举最后一批的起点 j+1，即切点 j 把前 j 个任务作为已处理前缀
        for (ll j = 0; j < i; j++) {
            ll cand = f[j] + (S + preT[i] - preT[j]) * (totalC - preC[j]);
            if (cand < best)
                best = cand;
        }
        f[i] = best;
    }

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

复杂度

• 时间复杂度：前缀和 $O(N)$，DP 双层枚举 $O(N^2)$；$N \leqslant 5000$ 时约 $1.25\times10^7$ 次 $O(1)$ 转移，与标准 C++ 解法同阶。
• 空间复杂度：两条前缀和 + 一个 f 数组，$O(N)$。
• 费用可达约 $2.5\times10^{11}$，超过 32 位整数；Python int 任意精度，无需额外处理。

总结

• 顺序固定 + 连续分批，是标准的区间划分 DP 结构；难点只在启动费 $S$ 的跨段耦合。
• 用交换求和次序把"每批影响未来"改写成"每批乘以它之后的 $C$ 后缀和"，耦合在记账层面消失，转移量全部前缀和化。
• 朴素的"完成时刻入状态"不可行，是因为完成时刻依赖前缀的具体划分而非仅依赖 $j$；换记账后状态只需 $j$ 这一个切点。
• $O(N^2)$ 即为本题正解量级，$N \leqslant 5000$ 下不需要斜率优化。