POJ 1180 Batch Scheduling（斜率优化DP）

题意：

黑书 152，任务调度问题。

思路：

1. 因为考虑到运行时间偏移，把 di 解释成：从任务 i 开始到 最后一个任务结束，最少的总代价;

2. d[i] = min(d[j] + w(j+1, i)); w(j+1, i) = (S + sumTi - sumTj) * sumFi;  其中 sumTi sumFi 分别表示 i 到 n 的和;

3. 典型的递推关系式，进一步化简有：di = dj - sumFi*sumTj + M;  M 看成是常量，Y = dj, X = sumTj, A = sumFi; A > 0 且单调增;

4. 利用下凸函数特性，以及斜率优化的知识，可以把算法优化到 O(n);

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 10010;
int sumf[MAXN], sumt[MAXN], Q[MAXN], N, S, dp[MAXN];

inline double slope(int i, int j) {
    return 1.0 * (dp[i]-dp[j]) / (sumt[i]-sumt[j]);
}

void workout() {
    int s = 0, e = -1;
    dp[N] = 0; Q[++e] = N;
    for (int i = N-1; i >= 0; i--) {
        while (s < e && slope(Q[s], Q[s+1]) <= (double)sumf[i])
            ++s;
        int j = Q[s];
        dp[i] = dp[j] - sumf[i]*sumt[j] + (S+sumt[i])*sumf[i];
        while (s < e && slope(Q[e], i) <= slope(Q[e], Q[e-1]))
            --e;
        Q[++e] = i;
    }
}

int main() {
    while (~scanf("%d", &N)) {
        scanf("%d", &S);
        for (int i = 0; i < N; i++)
            scanf("%d%d", &sumt[i], &sumf[i]);
        sumt[N] = sumf[N] = 0;
        for (int i = N-1; i >= 0; i--) {
            sumt[i] += sumt[i+1];
            sumf[i] += sumf[i+1];
        }
        workout();
        printf("%d\n", dp[0]);
    }
    return 0;
}