P5785 [SDOI2012] 任务安排

题目链接：P5785 [SDOI2012] 任务安排 - 洛谷。

本题是经典 DP 斜率优化题型。

题目描述

机器上有 $n$ 个需要处理的任务，它们构成了一个序列。这些任务被标号为 $1$ 到 $n$ ，因此序列的排列为 $1, 2, 3 \dots n$ 。这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T_{i}$ 。在每批任务开始前，机器需要启动时间 $s$ ，而完成这批任务所需的时间是各个任务需要时间的总和。

注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $C_{i}$ 。

请确定一个分组方案，使得总费用最小。

输入格式

第一行一个整数 $n$ 。

第二行一个整数 $s$ 。

接下来 $n$ 行，每行有一对整数，分别为 $T_{i}$ 和 $C_{i}$ ，表示第 $i$ 个任务单独完成所需的时间是 $T_{i}$ 及其费用系数 $C_{i}$ 。

输出格式

一行，一个整数，表示最小的总费用。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

对于 $100 %$ 数据， $1 \leq n \leq 3 \times 10^{5}$ ， $1 \leq s \leq 2^{8}$ ，$ \left| T_i \right| \le 2^8$， $0 \leq C_{i} \leq 2^{8}$ 。

题解

状态定义和转移

求出 $T, C$ 的前缀和 $sum T, sum C$ ，即 $sum T_{i} = \sum_{j = 1}^{i} T_{j}$ ， $sum C_{i} = \sum_{j = 1}^{i} C_{j}$ 。设 $f (i, j)$ 表示把前 $i$ 个任务分成 $j$ 批执行的最小费用，则第 $j$ 批任务完成的时间就是 $j \times S + sum T_{i}$ 。以第 $j - 1$ 批和第 $j$ 批任务的分界点为 DP 的“决策”，状态转移方程为：

f (i, j) = min_{0 \leq k < i} {f (k, j - 1) + (S \times j + sum T_{i}) \times (sum C_{i} - sum C_{k})}

该解法的时间复杂度为 $O (n^{3})$ 。

费用提前计算

本题并没有规定需要把任务分成多少批，在上一个解法中之所以需要批数 $j$ ，是因为我们需要知道机器启动了多少次（每次启动都要 $S$ 单位时间），从而计算出 $i$ 所在的一批任务的完成时刻。

事实上，在执行一批任务时，我们不容易直接得知在此之前机器启动过几次。但我们知道，机器因执行这批任务而花费的启动时间 $S$ ，会累加到在此之后所有任务的完成时刻上。设 $f (i)$ 表示把前 $i$ 个任务分成若干批执行的最小费用，状态转移方程为：

f (i) = min_{0 \leq j < i} {f (j) + sum T_{i} \times (sum C_{i} - sum C_{j}) + S \times (sum C_{n} - sum C_{j})}

在上式中，第 $j + 1$ 到 $i$ 个任务在同一批内完成， $sum T_{i}$ 是忽略机器的启动时间时，这批任务的完成时刻。因为这批任务的执行，机器的启动时间 $S$ 会对第 $j + 1$ 个之后的所有任务产生影响，故我们把这部分补充到费用中。

也就是说，我们没有直接求出每批任务的完成时刻，而是在一批任务“开始”对后续任务产生影响时，就先把费用累加到答案中。这是一种名为“费用提前计算”的经典思想。

该解法的时间复杂度为 $O (n^{2})$ 。

该解法可以通过本题的弱化版：【蓝色】P2365 任务安排 - 洛谷

斜率优化

将上述方程中仅与 $i$ 有关项、仅与 $j$ 有关项和与 $i, j$ 同时有关项分开，得到：

f (i) - sum T_{i} \times sum C_{i} - S \times sum C_{n} = min_{0 \leq j < i} {f (j) - sum T_{i} \times sum C_{j} - S \times sum C_{j}}

其中，我们令

\begin{aligned} b_{i} & =f(i)-sumT_{i}\timessumC_{i}-S\timessumC_{n} \\ k_{i} & =sumT_{i} \\ y_{j} & =f(j)-S\timessumC_{j} \\ x_{j} & =sumC_{j} \end{aligned}

则上式可写成

b_{i} = y_{j} - k_{i} \times x_{j}

目标是使得 $b_{i}$ 尽量小，且 $k_{i}$ 随 $i$ 增大而单调不减。这一性质与 P3195 [HNOI2008] 玩具装箱 | EagleBear2002 的博客中的斜率优化性质相同。按照同样的方式用单调队列维护下凸壳即可。

该算法复杂度为 $O (n)$ 。