维护上凸壳,但是每次检查队列似乎没有出队的元素?
帮忙看看吧/kel
#include<cstdio>
#include<cctype>
const int M=1e6+5;
typedef long long ll;
ll a,b,c,sum[M],dp[M];
int n,L=1,R,q[M];
inline double slope(int a,int b){
return 1.0*(dp[b]-dp[a])/(sum[b]-sum[a])+a*(sum[b]+sum[a]);
}
inline ll read(){
ll n=0;char s;bool f=true;
while(!isdigit(s=getchar()))if(s==45)f=false;
while(n=n*10+(s^48),isdigit(s=getchar()));
return f?n:-n;
}
inline void print(){
for(int i=L;i<=R;++i)printf("%d ",q[i]);
printf("\n");
}
signed main(){
int i,j,x;
n=read();a=read();b=read();c=read();
for(i=1;i<=n;++i){
sum[i]=read()+sum[i-1];
// print();
while(L<=R&&slope(q[L],q[L+1])<=2.0*a*sum[i])++L;
j=q[L];x=(sum[i]-sum[j]);
dp[i]=dp[j]+a*x*x+b*x+c;
// print();
while(L<=R&&slope(q[R-1],q[R])>=slope(q[R],i))--R;
q[++R]=i;
// print();
// printf("%d %lld|\n",j,dp[i]);
}
printf("%lld",dp[n]);
}