(Zj) a200. APIO2010 1.特别行动队 [dp斜率優化]

http://zerojudge.tw/ShowProblem?problemid=a200

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

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

LL p[MAX_N];
LL dp[MAX_N];
int v[MAX_N];

LL a,b,c;

struct line {
    LL m,b;
    LL val(LL x) {
        return m*x+b;
    }
};

deque<line> dq;

LL t(int i) {
    return a*p[i]*p[i] + b*p[i] + c;
}

LL f(int i) {
    return a*p[i]*p[i] - b*p[i] + dp[i];
}

LL g(int i) {
    return p[i];
}

LL h(int i) {
    return -2 * a * p[i];
}

bool check(line x,line y,line z) {
    return (x.b-z.b)*(y.m-x.m)<=(z.m-x.m)*(x.b-y.b);
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        scanf("%lld %lld %lld",&a,&b,&c);
        p[0]=0;
        for (int x=1;n>=x;x++) {
            scanf("%d",&v[x]);
            p[x]=p[x-1]+v[x];
        }
        dp[0] = t(0);
        dq.clear();
        dq.push_back((line){0,0});
        for (int i=1;n>=i;i++) {
            while (dq.size() >= 2 && dq[0].val(g(i)) < dq[1].val(g(i))) dq.pop_front();
            dp[i] = dq[0].val(g(i)) + t(i);
            line newline{h(i),f(i)};
            while (dq.size() >= 2 && check(dq[dq.size()-2],dq[dq.size()-1],newline)) {
                dq.pop_back();
            }
            dq.push_back(newline);
        }
        printf("%lld\n",dp[n]);
    }
}

相似題：http://acm.hdu.edu.cn/showproblem.php?pid=3507