bzoj1911: [Apio2010]特别行动队

首页 > 代码库 > bzoj1911: [Apio2010]特别行动队

bzoj1911: [Apio2010]特别行动队

2024-08-12 20:47:46 217人阅读

斜率优化

//f[i]=max(f[j-1]+a(sum[i]-sum[j-1])^2+b(sum[i]-sum[j-1])+c) (1<=j<=i)

//g[j]>g[k]=>f[j-1]+a(sum[i]-sum[j-1])^2-bsum[j-1])<f[k-1]+a(sum[i]-sum[k-1])^2-bsum[k-1]

//=>f[j-1]-f[k-1]-bsum[j-1]+bsum[k-1]+sum[j-1]^2-sum[k-1]^2<2a(sum[j-1]-sum[k-1])sum[i];

//=>g[j]=f[j]-bsum[j]+ sum[j]^2

//=>g[j]-g[k]/2a(sum[j]-sum[k])<sum[i];

//=>队首维护X(front+1,front)<=sum[i] front++;

//=>队尾维护X(i,tail)<=X(tail,tail-1) tail--;

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longint read(){    int x=0,f=1;char c=getchar();    while(!isdigit(c)){        if(c==‘-‘) f=-1;c=getchar();    }    while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();    return x*f;} const int nmax=1000005;ll sum[nmax],f[nmax],a,b,c,n;int q[nmax];double G(int j,int k){    double ta=f[j]-b*sum[j]+a*sum[j]*sum[j]-f[k]+b*sum[k]-a*sum[k]*sum[k];    double tb=2*a*(sum[j]-sum[k]);    return ta/tb;}int main(){    n=read(),a=read(),b=read(),c=read();    rep(i,1,n) sum[i]=sum[i-1]+read();    int l=1,r=1;q[1]=0;    rep(i,1,n){        while(l<=r-1&&G(q[l+1],q[l])<=sum[i]) l++;        f[i]=f[q[l]]+a*(sum[i]-sum[q[l]])*(sum[i]-sum[q[l]])+b*(sum[i]-sum[q[l]])+c;        while(l<=r-1&&G(i,q[r])<=G(q[r],q[r-1])) r--;        q[++r]=i;    }    printf("%lld\n",f[n]);    return 0;}