【BZOJ 1911】 [Apio2010]特别行动队

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

HINT

转移方程

f[i]=max(f[j]+a*(h[i]-h[j])^2+b*(h[i]-h[j])+c)

//h数组为前缀和

如此显然的方程复杂度是O（n^2） 的

设j>k且j比k右，则有
f[j]+a*(h[i]-h[j])^2+b*(h[i]-h[j])+c>f[k]+a*(h[i]-h[k])^2+b*(h[i]-h[k])+c
移项可得
f[j]-f[k]+a*h[j]^2-a*h[k]^2-b*h[j]+b*h[k]>2*a*(h[j]-h[k])*h[i]
由此方程我们可以建立一个队列
当队首元素与第二个元素k,j不满足上式时，队首++
取出第一个元素O(1)的更新f[j]
判断队尾的两个元素，以维护上凸的性质

 #include<cstdio>
 #define ll long long
 const int N=;
 int a,b,c,n,l,r;
 int x[N],q[N];
 ll f[N],h[N];
 ll sqr(ll x) {return x*x;}
 double slop(int k,int j)
 {return (double)(f[j]-f[k]+a*sqr(h[j])-a*sqr(h[k])-b*h[j]+b*h[k])/(double)(*a*(h[j]-h[k]));}

 int main(){
     scanf("%d",&n);
     scanf("%d%d%d",&a,&b,&c);
     for (int i=;i<=n;i++) {
         scanf("%d",&x[i]);
         h[i]=h[i-]+x[i];
     }
     for (int i=;i<=n;i++){
         while(l<r&&slop(q[l],q[l+])<h[i])l++;
         int now=q[l];
         f[i]=f[now]+a*sqr((h[i]-h[now]))+b*(h[i]-h[now])+c;
         while(l<r&&slop(q[r],i)<slop(q[r-],q[r])) r--;
         q[++r]=i;
     }
     printf("%lld",f[n]);
 }