$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)$
最后一次更新于2019-11-14
0 条评论