$f_{i}=\max\{f_j+a*(s_i-s_j)^2+b*(s_i-s_j)+c\}$

$f_i=\max\{f_j+a*({s_i}^2-2*s_i*s_j+{s_j}^2)+b*(s_i-s_j)+c\}$

转化成关于$f_j+a*{s_j}^2-b*s_j=2*a*s_i*s_j+f_i-a*{s_i}^2-b*s_i-c$的直线,

那么请注意,由于$a$是负数,那么斜率单调递减,并且要求截距最大,因此需要维护一个上凸壳。

比较斜率用这个东西

$(f_k+a*{s_k}^2-b*s_k)-(f_j+a*{s_j}^2-b*s_j)\ge 2*a*s_i*(s_k-s_j)$