题目链接：P5785 [SDOI2012] 任务安排 - 洛谷。
本题是经典 DP 斜率优化题型。
题目描述
机器上有 $n$ 个需要处理的任务，它们构成了一个序列。这些任务被标号为 $1$ 到 $n$，因此序列的排列为 $1 , 2 , 3 \cdots n$。这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T_i$。在每批任务开始前，机器需要启动时间 $s$，而完成这批任务所需的时间是各个任务需要时间的总和。
注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。
请确定一个分组方案，使得总费用最小。
输入格式
第一行一个整数 $n$。
第二行一个整数 $s$。
接下来 $n$ 行，每行有一对整数，分别为 $T_i$ 和 $C_i$，表示第 $i$ 个任务单独完成所需的时间是 $T_i$ 及其费用系数 $C_i$。
输出格式
一行，一个整数，表示最小的总费用。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
说明/提示
对于 $100%$ 数据，$1 \le n \le 3 \times 10^5$，$1 \le s \le 2^8$，$ \left| T_i \right| \le 2^8$，$0 \le C_i \le 2^8$。
题解
状态定义和转移
求出 $T, C$ 的前缀和 $\text{sum}T, \text{sum}C$，即 $\text{sum}T_i = \sum_{j=1}^{i} T_j$，$\text{sum}C_i = \sum_{j=1}^{i} C_j$。设 $f(i,j)$ 表示把前 $i$ 个任务分成 $j$ 批执行的最小费用，则第 $j$ 批任务完成的时间就是 $j \times S + \text{sum}T_i$。以第 $j-1$ 批和第 $j$ 批任务的分界点为 DP 的“决策”，状态转移方程为：
$$ f(i,j) = \min_{0 \leq k < i} \set{ f(k,j-1) + (S \times j + \text{sum}T_i) \times (\text{sum}C_i - \text{sum}C_k) } $$
该解法的时间复杂度为 $O(n^3)$。
费用提前计算
本题并没有规定需要把任务分成多少批，在上一个解法中之所以需要批数 $j$，是因为我们需要知道机器启动了多少次（每次启动都要 $S$ 单位时间），从而计算出 $i$ 所在的一批任务的完成时刻。
事实上，在执行一批任务时，我们不容易直接得知在此之前机器启动过几次。但我们知道，机器因执行这批任务而花费的启动时间 $S$，会累加到在此之后所有任务的完成时刻上。设 $f(i)$ 表示把前 $i$ 个任务分成若干批执行的最小费用，状态转移方程为：
$$ f(i) = \min_{0 \leq j < i} \set{ f(j) + \text{sum}T_i \times (\text{sum}C_i - \text{sum}C_j) + S \times (\text{sum}C_n - \text{sum}C_j) } $$
在上式中，第 $j+1$ 到 $i$ 个任务在同一批内完成，$\text{sum}T_i$ 是忽略机器的启动时间时，这批任务的完成时刻。因为这批任务的执行，机器的启动时间 $S$ 会对第 $j+1$ 个之后的所有任务产生影响，故我们把这部分补充到费用中。
也就是说，我们没有直接求出每批任务的完成时刻，而是在一批任务“开始”对后续任务产生影响时，就先把费用累加到答案中。这是一种名为“费用提前计算”的经典思想。
该解法的时间复杂度为 $O(n^2)$，可以通过本题的弱化版：【蓝色】P2365 任务安排 - 洛谷
斜率优化
将上述方程中仅与 $i$ 有关项、仅与 $j$ 有关项和与 $i,j$ 同时有关项分开，得到：
$$ f(i) - \text{sum}T_i \times \text{sum}C_i - S \times \text{sum}C_n = \min_{0 \leq j < i} \set{ f(j) - \text{sum}T_i \times \text{sum}C_j - S \times \text{sum}C_j} $$
其中，我们令
$$ \begin{align*} b_i & = f(i) - \text{sum}T_i \times \text{sum}C_i - S \times \text{sum}C_n \ k_i & = \text{sum}T_i \ y_j & = f(j) - S \times \text{sum}C_j \ x_j & = \text{sum}C_j \end{align*} $$
则上式可写成
$$ b_i = y_j - k_i \times x_j $$
目标是使得 $b_i$ 尽量小，且 $k_i$ 随 $i$ 增大而单调不减。这一性质与 P3195 [HNOI2008] 玩具装箱 | EagleBear2002 的博客 中的斜率优化性质相同。按照同样的方式用单调队列维护下凸壳即可。
该算法复杂度为 $O(n)$。
