安利蒟蒻斜率优化总结
由于人是每次都是连续一段一段地选，所以考虑直接对(x)记前缀和，设现在的(x_i=)原来的(sumlimits_{j=1}^ix_i)。
设(f_i)为安排前(i)个人的最大值((f_0=0))
(f_i=maxlimits_{j=0}^{i-1}{f_j+a(x_i-x_j)^2+b(x_i-x_j)+c})
(quad=maxlimits_{j=0}^{i-1}{f_j-2ax_ix_j+ax_j^2-bx_j}+ax_i^2+bx_i+c)
决策(j)比(k)优当且仅当
[f_j-2ax_ix_j+ax_j^2-bx_jge f_k-2ax_ix_k+ax_k^2-bx_k
]
[frac{f_j+ax_j^2-bx_j-(f_k+ax_k^2-bx_k)}{x_j-x_k}ge 2ax_i
]
于是每个决策可以看成是一个点((x_i,y_i)(y_i=f_i+ax_i^2-bx_i))
不用考虑变号。因为(a<0)，(x_i)递增，斜率(2ax_i)递减，所以我们用单调队列维护一个下凸包就行了。依旧是维护队首为当前最优解。
当然注意这里的转移是从(0)到(i-1)，所以和土地征用有点点不一样，要先求出(f_i)再加入决策点(i)。
纯天然代码
#include<cstdio>
#define RG register
#define R RG int
#define G c=getchar()
#define Calc(j,k) (y[j]-y[k])/(x[j]-x[k])//求斜率
const int N=1e6+9;
int q[N];
double f[N],k[N],x[N],y[N];//变量名同上
inline int in(){
RG char G;RG bool f=0;
while(c<'-')G;
if(c=='-')f=1,G;
R x=c&15;G;
while(c>'-')x=x*10+(c&15),G;
return f?-x:x;
}
int main(){
R n=in(),i,h,t;
RG double a=in(),b=in(),c=in(),now;
for(i=h=t=1;i<=n;++i){
x[i]=x[i-1]+in();//前缀和
now=2*a*x[i];//当前斜率
while(h<t&&k[h]>=now)++h;
f[i]=-now*x[q[h]]+y[q[h]]+(a*x[i]+b)*x[i]+c;//先求fi,根据定义式求
y[i]=f[i]+(a*x[i]-b)*x[i];//yi跟着求
while(h<t&&k[t-1]<=Calc(q[t],i))--t;//维护凸包
k[t]=Calc(q[t],i);q[++t]=i;
}
printf("%.0lf
",f[n]);
return 0;
}