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

Posted by xiaodao
Category: 日常
Tags: 斜率 DP