### Brief description:

N個任務排成一個序列在一台機器上等待完成（順序不得改變），這 N 個任務被分成若干批，每批包含相鄰的若干任務。

從時刻 0 開始，這些任務被分批加工，第i個任務單獨完成所需的時間是 Ti。在每批任務開始前，機器需要啟動時間 S，

而完成這批任務所需的時間是各個任務需要時間的總和（同一批任務將在同一時刻完成）。

每個任務的費用是它的完成時刻乘以一個費用係數Fi。請確定一個分組方案，使得總費用最小。（1 <= N <= 10000）

### Analysis:

調整 $$T_i$$ 為前綴和，$$F_i$$ 為後綴和。

$$! \begin{aligned} f_i &= \min_{0 \leq j < i}\big\{ f_j + ((T_i+S)-T_j)F_{j+1} \big\} \\ &= \min_{0 \leq j < i}\big\{(T_i+S)F_{j_1} + (f_j - F_{j+1}T_j) \end{aligned} $$ 寫成斜率優化的標準形式，b = kx + y 這裡有：

- $$k = T_i + S$$
- $$x = F_{j+1} $$
- $$y = f_j – F_{j+1}T_j $$

這裡 $$x$$ 和 $$k$$ 均單調，單調隊列即可。

//}/* .................................................................................................................................. */ const int N = int(1e4) + 9; int _T[N], _F[N], T[N], F[N]; int q[N], cz, op; LL f[N]; int n, S; #define k (LL)(T[i]+S) #define x(j) (F[j+1]) #define y(j) (f[j]-(LL)T[j]*F[j+1]) #define eval(j) (k*x(j) + y(j)) LL det(LL x1, LL y1, LL x2, LL y2){ return x1*y2 - x2*y1; } int dett(int p0, int p1, int p2){ LL t = det(x(p1)-x(p0), y(p1)-y(p0), x(p2)-x(p0), y(p2)-y(p0)); return t < 0 ? -1 : t > 0; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif while (~scanf("%d", &n)){ RD(S); REP_1(i, n){ RD(_T[i], _F[i]); T[i] = T[i-1] + _T[i]; } F[n] = _F[n]; DWN(i, n, 0) F[i] = F[i+1] + _F[i]; int cz = 0, op = 0; REP_1(i, n){ while (cz < op && eval(q[cz]) >= eval(q[cz+1])) ++cz; f[i] = eval(q[cz]); while (cz < op && dett(q[op-1], q[op], i) >= 0) --op; q[++op] = i; } OT(f[n]); } }

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2801195