BZOJ1911 [Apio2010]特别行动队 【斜率优化】

Description

Input

Output

Sample Input

Sample Output

HINT

一定要好好纪念一下QAQ，本蒟蒻第一次自己推出斜率优化dp

有点模糊惹。。将就一下【捂脸】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define eps 1e-9
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 1000005,maxm = 100005,INF = 1000000000;
inline int read(){int out = 0,flag = 1;char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}return out * flag;
}
int n,a,b,c,q[maxn],head,tail;
LL sum[maxn],f[maxn];
inline double slope(int u,int v){double y1 = f[u] + a * sum[u] * sum[u] - b * sum[u],y2 = f[v] + a * sum[v] * sum[v] - b * sum[v];return (y1 - y2) / (sum[u] - sum[v]);
}
inline LL g(LL x){return a * x * x + b * x + c;
}
inline LL getf(int i,int j){return f[j] + g(sum[i] - sum[j]);
}
int main()
{n = read(); a = read(); b = read(); c = read();REP(i,n) sum[i] = sum[i - 1] + read();head = tail = 0;for (int i = 1; i <= n; i++){while (head < tail && slope(q[head],q[head + 1]) + eps > 2 * a * sum[i])head++;f[i] = getf(i,q[head]);while (head < tail && slope(q[tail],q[tail - 1]) < slope(i,q[tail]) + eps)tail--;q[++tail] = i;}cout << f[n] << endl;return 0;
}