(POJ) 1180 -- Batch Scheduling

http://poj.org/problem?id=1180

我是用斜率優化，也可以用Monge Condition 優化成 O(N lg N)

#include <iostream>
#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;

//dp[i] = min(dp[j] + (s+pt[i]-pt[j]) * (pp[n] - pp[j]))

typedef long long LL;
const int MAX_N = 1e4 + 6;

LL dp[MAX_N],pt[MAX_N],pp[MAX_N],s;
int n;

LL tt[MAX_N],p[MAX_N];

LL f(LL i) {
    return s*pp[n] + pt[i]*pp[n];
}

LL g(LL j) {
    return dp[j] - pt[j]*pp[n] + pt[j]*pp[j] - s*pp[j];
}

LL h(LL i) {
    return -pt[i];
}

LL t(LL j) {
    return pp[j];
}

struct Line {
    LL m,b;
    Line(LL _m, LL _b) {
        m=_m;
        b=_b;
    }
    LL val(LL x) {
        return m*x+b;
    }
};

bool check(Line _1,Line _2,Line _3) {
    return (_1.m-_3.m)*(_1.b-_2.b) <= (_1.b-_3.b)*(_1.m-_2.m);
}

int main () {
    while (scanf("%d",&n) != EOF) {
        scanf("%lld",&s);
        for (int i=1;n>=i;i++) {
            scanf("%lld %lld",&tt[i],&p[i]);
            pt[i] = pt[i-1]+tt[i];
            pp[i] = pp[i-1]+p[i];
        }
        deque<Line> dq;
        dq.push_back(Line(t(0),g(0)));
        for (int i=1;n>=i;i++) {
            while (dq.size()>1 && dq[0].val(h(i)) > dq[1].val(h(i))) dq.pop_front();
            dp[i] = f(i) + dq[0].val(h(i));
            Line newline=Line(t(i),g(i));
            while (dq.size()>1 && check(newline,dq[dq.size()-1],dq[dq.size()-2])) {
                dq.pop_back();
            }
            dq.push_back(newline);
        }
        printf("%lld\n",dp[n]);
    }
}