【BZOJ 1911】【codevs 1318】特別行動隊、スロープ最適化DP

転送ゲート1転送ゲート2は前に書く:OIを一時停止する1週間、文化課の構想を補う:転送方程式f[i]=max(f[j]+a(sum[i]−sum[j])2+b(sum[i]−sum[j])+c)x>yを設定しx比yが優れている場合(f[x]−f[y])/(sum[x]−sum[y])+a

#include<bits/stdc++.h>
#define LL long long
#define M 1000002
using namespace std;
int n,a,b,c,x,head=1,tail=1;
int sum[M],q[M];
LL f[M];
int in()
{
    int f=1,t=0;char ch=getchar();
    while (ch>'9'||ch<'0')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') t=(t<<3)+(t<<1)+ch-'0',ch=getchar();
    return f*t;
}
double Get(int x,int y)
{
    return (double)(f[x]-f[y])/(double)(sum[x]-sum[y])+(LL)a*(sum[x]+sum[y])-b;
}
main()
{
    n=in();
    a=in();b=in();c=in();
    for (int i=1;i<=n;i++) x=in(),sum[i]=sum[i-1]+x;
    for (int i=1;i<=n;i++)
    {
        while (head<tail&&Get(q[head+1],q[head])>2*a*sum[i]) head++;
        LL x=sum[i]-sum[q[head]];
        f[i]=f[q[head]]+a*x*x+b*x+c;
        while (head<tail&&Get(i,q[tail])>Get(q[tail],q[tail-1])) tail--;
        q[++tail]=i;
    }
    printf("%lld",f[n]);
}