形式化题目

把序列 $T_1,\dots,T_N$ 划分成若干段连续的批次。批次的执行按顺序进行：机器从时刻 $0$ 开始，处理每批前先等待启动时间 $S$，批内任务依次执行 $T_i$，一批的所有任务在整批结束时同时完成。任务 $i$ 的费用为「所在批的完成时刻 $\times\, C_i$」，求总费用的最小值。

正解

思路

第一步：朴素分批 DP。 设 $f[i][j]$ 表示前 $i$ 个任务分成 $j$ 批的最小总费用。转移时枚举最后一批的开头 $k$，需要知道这批的完成时刻，也就是前面 $j-1$ 批的总耗时。这样状态 $O(n^2)$、转移 $O(n)$，对 $n=5000$ 太慢。更麻烦的是，费用依赖「完成时刻」这个绝对量，状态被迫把时间轴背在身上。

第二步：费用提前计算，砍掉一维。 关键观察：每开一批，启动时间 $S$ 会让这一批以及之后所有任务的完成时刻都延后 $S$。那么在「决定新开一批」的时刻，它对总费用的全部影响就已经确定：$S \times$（尚未完成的任务的 $C$ 之和）$ = s\cdot(c[n]-c[j])，其中 $c 是 $C$ 的前缀和。于是批次数这一维毫无必要——未来的影响现在一次算清：

其中 $t[i]$ 是 $T$ 的前缀和，含义是：最后一批为 $j+1 \dots i$，这批内所有任务都在时刻 $t[i]$ 完成（贡献 $t[i]\cdot(c[i]-c[j])$），同时把启动时间 $S$ 对后段的影响提前记为 $s\cdot(c[n]-c[j])$。样例的最优分批如下：

合计 $25+30+98=153$，与样例一致。

第三步：把转移看成几何问题。 把与 $j$ 有关的项整理成「斜率 × 横坐标 + 截距」的形状。固定 $i$，令

则

花括号里是过点 $P_j$、斜率为 $k$ 的直线的截距：min 取到时，$P_j$ 恰好落在这些点构成的上边缘被斜率为 $k$ 的直线撑到的位置。等价地说，只需对每个 $i$ 在二维点集上求「斜率 $k$ 方向的极值」。

第四步：两个单调性 → 下凸壳 + 单调队列。

• $c$ 非负，所以 $x_j = c[j]$ 随 $j$ 递增：新点只会从右侧插入，点集维持一个下凸壳即可（最小截距只会由凸壳上的点取到，凸壳内的点永远不优）。
• $t$ 非负，所以查询斜率 $k = t[i]+s$ 随 $i$ 递增：在凸壳上，若队首到第二点的边斜率 $\leqslant k$，则第二点的截距不会更大，队首永久淘汰。队首指针、队尾插入都只前进，每个点至多进出队一次。

于是每个 $i$ 均 $O(1)$ 摊还，总复杂度 $O(n)$。转移与查询的过程如下：

flowchart LR
    A["队列: P0 ... Pm<br/>下凸壳, x 递增"] --> B{"队首到下一点<br/>斜率 &le; k = t[i]+s ?"}
    B -- 是 --> C["队首已不可能更优<br/>永久弹出"]
    C --> B
    B -- 否 --> D["用队首 P_j 计算<br/>f[i] = y_j - k*x_j + t[i]*c[i] + s*c[n]"]
    D --> E["新点 P_i = (c[i], f[i])<br/>从队尾弹出被压住的点"]
    E --> F["P_i 入队, 处理 i+1"]
    F --> A

观察要点：队首判定是「斜率比较」而非「值比较」——一旦边斜率被 $k$ 超过，随着 $k$ 继续增大这条边永远不会再被选中，所以弹出是安全的；队尾判定保证队列中相邻两点连成的折线斜率严格递增，这正是下凸壳的形状条件。

代码

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <cstdio>
#include <deque>
using namespace std;

typedef long long ll;

const int MAXN = 5005;

ll task_time[MAXN]; // 第 i 个任务的执行时间 T_i
ll task_cost[MAXN]; // 第 i 个任务的费用系数 C_i
ll n, s;

deque<pair<ll, ll> > hull; // 下凸壳上的直线 (斜率 m, 截距 b)，斜率随插入递减

// 把直线 y = m*x + b 压入凸壳尾部。
// 若队尾直线在新直线与次队尾直线的交点之上（三点不再构成下凸），它永远取不到最小值，弹掉。
void push_line(ll m, ll b) {
    while (hull.size() >= 2) {
        ll m1 = hull[hull.size() - 2].first, b1 = hull[hull.size() - 2].second;
        ll m2 = hull[hull.size() - 1].first, b2 = hull[hull.size() - 1].second;
        if ((b2 - b1) * (m2 - m) < (b - b2) * (m1 - m2)) break; // 队尾仍是凸壳顶点
        hull.pop_back();
    }
    hull.push_back(make_pair(m, b));
}

// 查询所有已插入直线在 x 处的最小值。
// 查询点 x 严格递增，最优直线沿凸壳单调右移，队首弹出即可均摊 O(1)。
ll min_line(ll x) {
    while (hull.size() >= 2
           && hull[0].first * x + hull[0].second >= hull[1].first * x + hull[1].second)
        hull.pop_front();
    return hull[0].first * x + hull[0].second;
}

int main() {
    scanf("%lld%lld", &n, &s); // S 是每批任务开始前的启动时间
    ll total_cost = 0;
    for (ll i = 1; i <= n; i++) {
        scanf("%lld%lld", &task_time[i], &task_cost[i]);
        total_cost += task_cost[i];
    }
    // f[i]：前 i 个任务的最小总费用（已把启动时间折算给「它及之后所有任务」）
    // f[i] = sc[i]*st[i] + S*total_cost + min_j { -sc[j]*(st[i]+S) + f[j] }
    // 每个决策 j 是一条斜率 -sc[j] 递减的直线，查询点 st[i]+S 递增 → 单调队列凸壳
    ll dp = 0, st = 0, sc = 0; // dp = f[0] = 0
    for (ll i = 1; i <= n; i++) {
        push_line(-sc, dp); // 此刻 sc、dp 仍是第 i-1 轮的值
        st += task_time[i];
        sc += task_cost[i];
        dp = sc * st + s * total_cost + min_line(st + s);
    }
    printf("%lld\n", dp);
    return 0;
}

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#!/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-10-01 21:45
# update_at: 2026-10-01 21:45

import sys
from collections import deque
from itertools import accumulate


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

    # 每个任务给出一对 (T_i, C_i)，先成对读入再分别求前缀和
    tc = [(next(data), next(data)) for _ in range(n)]
    t = [0, *accumulate(x for x, _ in tc)]  # t[i] = 前 i 个任务的时间之和
    c = [0, *accumulate(y for _, y in tc)]  # c[i] = 前 i 个任务的费用系数之和

    # f[i]：前 i 个任务全部完成的最小总费用（费用提前计算）。
    # f[i] = t[i]*(c[i]-c[j]) + s*(c[n]-c[j]) + f[j]，
    # 整理成截距形式：f[i] = t[i]*c[i] + s*c[n] + min{ f[j] - (t[i]+s)*c[j] }，
    # 花括号内即「点 (c[j], f[j]) 在斜率 k = t[i]+s 下的 y-kx 最小值」→ 下凸壳 + 单调队列。
    f = [0] * (n + 1)
    hull = deque([(0, 0)])  # 下凸壳上的点 (x, y) = (c[j], f[j])，x 随插入严格递增

    for i in range(1, n + 1):
        k = t[i] + s  # 查询斜率，随 i 单调递增

        # 队首不再最优：若到第二点的边斜率 \leqslant k，则第二点的截距更小（或相等）
        while len(hull) >= 2 and hull[1][1] - hull[0][1] <= k * (hull[1][0] - hull[0][0]):
            hull.popleft()

        best_x, best_y = hull[0]
        f[i] = best_y - k * best_x + t[i] * c[i] + s * c[n]

        # 插入新点 (c[i], f[i])：中间点落在连线上方（含共线）则破坏下凸性，弹出
        new = (c[i], f[i])
        while len(hull) >= 2 and (
            (hull[-1][1] - hull[-2][1]) * (new[0] - hull[-2][0])
            >= (new[1] - hull[-2][1]) * (hull[-1][0] - hull[-2][0])
        ):
            hull.pop()
        hull.append(new)

    print(f[n])


if __name__ == "__main__":
    solve()

复杂度

• 时间 $O(n)$：每个点至多入队、出队各一次。
• 空间 $O(n)$：前缀和、$f$ 数组与凸壳队列。
• 费用上界约 $1.3\times 10^{14}$，超过 32 位整数范围（C++ 需 long long）；Python 整数天然无溢出。

总结

• 费用提前计算是处理「开始时间影响后续所有贡献」类分批问题的通用手法：在决策点把对未来的影响一次算清，用后缀和（这里是 $c[n]-c[j]$）代替对未来的模拟，状态从二维降到一维。
• 斜率优化的识别信号：一维 DP 转移形如 $f[i]=\min\{f[j]+与 i 有关项 \times 与 j 有关项 + \dots\}$，把 $j$ 相关部分拆成 $(x_j, y_j)$ 与查询斜率 $k_i$；再核对 $x_j$ 与 $k_i$ 是否都单调，若单调就用下凸壳 + 单调队列做到均摊 $O(1)$。
• 实现细节：队首/队尾判定全部用交叉乘避免除法；共线时（队首用 $\leqslant$、队尾用 $\geqslant$）保留更晚的点不影响正确性。
• 本题是「任务安排」系列的第一题：$N \leqslant 5000$ 时 $O(n^2)$ 也能过，但 $O(n)$ 的斜率优化写法是后续加强版（$N \leqslant 3\times10^5$，且 $T_i$、$C_i$ 可为负导致单调性被破坏）的必经之路。