BZOJ1911 [APIO2010] 特别行动队

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #define rep(i,l,r) for(int i=l; i<=r; i++)
 6 #define clr(x,y) memset(x,y,sizeof(x))
 7 using namespace std;
 8 typedef long long ll;
 9 const int maxn = 1000010;
10 ll n,A,B,C,head,tail,f[maxn],q[maxn],s[maxn];
11 inline ll read(){
12     ll ans = 0, f = 1;
13     char c = getchar();
14     for(; !isdigit(c); c = getchar())
15     if (c == ‘-‘) f = -1;
16     for(; isdigit(c); c = getchar())
17     ans = ans * 10 + c - ‘0‘;
18     return ans * f;
19 }
20 inline ll calc(int x){
21     return f[x] + A * s[x] * s[x];
22 }
23 inline ll get(int i,int j){
24     return f[j] + A * (s[i] - s[j]) * (s[i] - s[j]) + B * (s[i] - s[j]) + C;
25 }
26 int main(){
27     n = read(); A = read(); B = read(); C = read();
28     rep(i,1,n) s[i] = s[i-1] + read();
29     head = tail = f[0] = q[0] = 0;
30     rep(i,1,n){
31         while (head < tail && calc(q[head+1]) - calc(q[head]) >= (2 * A * s[i] + B) * (s[q[head+1]] - s[q[head]])) head++;
32         f[i] = get(i,q[head]);
33         while (head < tail && (calc(q[tail]) - calc(q[tail-1])) * (s[i] - s[q[tail]]) <= (calc(i) - calc(q[tail])) * (s[q[tail]] - s[q[tail-1]])) tail--;
34         q[++tail] = i;
35     }
36     printf("%lld\n",f[n]);
37     return 0;
38 }