ModestCoder_的博客

原题传送门斜率优化令si=∑j=1icjs_i=\sum_{j=1}^{i}c_jsi​=∑j=1i​cj​可以写出一个非常显然的dp方程：dpi=min(dpj+(si−sj)2)+Mdp_i=min(dp_j+(s_i-s_j)^2)+Mdpi​=min(dpj​+(si​−sj​)2)+M接下来固定套路设两个决策x,y(x>y)x,y(x>y)x,y(x...