题目

\(N\) 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 \(N\) 个任务被分成若干批，每批包含相邻的若干任务。从时刻 \(0\) 开始，这些任务被分批加工，第 \(i\) 个任务单独完成所需的时间是 \(T_i\)。在每批任务开始前，机器需要启动时间 \(S\)，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数 \(F_i\)。请确定一个分组方案，使得总费用最小。

分析

可以使用费用提前计算的技巧，把后面的费用移到前面计算。

设 \(d_i\) 代表到前 \(i\) 个任务的最小代价：\(F,T\) 分别为 \(f,t\) 数组的前缀和

\[ \begin{align*} d_i & = \min_{j=0}^{i-1} \{d_j + S(F_n - F_j) + T_i (F_i - F_j)\} \\ & = \min_{j=0}^{i-1} \{d_j + S F_n - S F_j + T_i F_i - T_i F_j\} \\ & = \min_{j=0}^{i-1} \{d_j - S F_j - T_i F_j\} + T_i F_i + S F_n \\ \end{align*} \]

令：\(b = d_j - ST_j - T_iF_j\), 则有：

\[ \begin{align*} b & = d_j - SF_j - T_iF_j\\ d_j - SF_j & = b + T_iF_j \\ \end{align*} \]

令 \(y=d_j-SF_j\), \(x=F_j\), \(k = T_i\), 这就是我们常见的斜率优化式。

显然 \(T_i\) 单调递增。

代码

#include 
    
     int const kMaxN = 1e6 + 5;std::deque
     
       que;int d[kMaxN], f[kMaxN], t[kMaxN], F[kMaxN], T[kMaxN], S, n;inline int X(int i) {return F[i];}inline int Y(int i) {return d[i] - S * F[i];}inline double Slope(int i, int j) {return (Y(i) - Y(j)) / (double)(X(i) - X(j));}int main() {    memset(d, 0x3f, sizeof(d));    scanf("%d%d", &n, &S);    for(int i = 1; i <= n; i++) {        scanf("%d%d", t + i, f + i);        T[i] = T[i - 1] + t[i];        F[i] = F[i - 1] + f[i];    }    d[0] = 0;    que.push_back(0);    for(int i = 1; i <= n; i++) {        while(que.size() > 1 && Slope(que[0], que[1]) < T[i]) que.pop_front();        int j = que[0];        d[i] = d[j] + S * (F[n] - F[j]) + T[i] * (F[i] - F[j]);        while(que.size() > 1 &&            Slope(que.back(), i) < Slope(que.back(), que[que.size() - 2])        )            que.pop_back();        que.push_back(i);    }    printf("%d", d[n]);    return 0;}