斜率优化dp

【模板】任务安排

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

同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 C_i。

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

先设计 \(dp\) 状态，显然可以 \(dp_{i,j}\) 表示把前 \(i\) 个任务分配进前 \(j\) 组里，令 \(t_i\) 表示时间的前缀和数组，\(c_i\) 表示贡献的前缀和数组，转移的时候枚举第 \(j-1\) 个区间的终点 \(k\)，\(dp_{i,j}=\min({dp_{k,j-1}+(j*s+t_i)*(c_i-c_k)})\) ，其中 \(j*s\) 表示前 \(j\) 个区间中重新启动产生的总贡献，\(t_i\) 即为花费的时间，\(c_i-c_k\) 为价值和。

\(O(n^3)\) 时间空间全寄，考虑优化。发现如果想把 \(j\) 这一维缩掉，转移方程中唯一与他有关的就是重新启动的贡献 \(s*j\)。那么我们可以换一种统计方式，不在枚举每个 \(i\) 时统计前面所有段对当前段的的贡献，我们直接在统计当前段（新开段）的时候提前把他对后面产生的贡献加上，这样与一开始的转移方程是等价的。

这种思想是一种名为费用提前计算的经典思想。

新开的转移方程为 \(dp_i\) 表示前 \(i\) 个任务最小贡献，前缀和意义不变，依然枚举上一个区间的终点 \(k\)，\(dp_i=\min (p_j+(c_n-c_k)*s+t_i*(c_i-c_k))\)，其中 \((c_n-c_k)*s\) 表示分段后他对于后面每一段都贡献了一个 \(s\)。

现在时间是 \(O(n^2)\) 的了，可以通过弱化版。

考虑怎么在缩减时间复杂度，