斜率优化学习笔记

        经典问题：BZOJ1010玩具装箱。http://zarxdy34.is-programmer.com/posts/185182.html

        题目大意：将数列\(\{a_n\}\)分成若干段，每一段的权值为\((\sum_{l<=i<=r}{C_i}+r-l-L)^2\)，求权值和的最小值。

        记\(sum_i=\sum_{j=1}^iC_j\)，可以写出DP方程\[f_i=min\{f_j+(i-(j+1)+sum_i-sum_j-L)^2\}(0<=j<i)\]

        将式子展开，合并含j的项，可以得到\[f_i=min\{f_j+(j+1+sum_j)^2-2(j+1+sum_j)(i+sum[i]-L)+(i+sum[i]-L)^2\}\]

        记\(a_i=f_i+(i+1+sum_i)^2,b_i=2(i+1+sum_i)\)，那么上式化简为\[f_i=min\{a_j-b_j(i+sum_i-l)\}+(i+sum_i-L)^2\]

        再记\(t=i+sum[i]-L\)，上式再化简为\[f_i=min\{a_j-tb_j\}+t^2\]

        显然我们要找的是使得答案最小的\(a_j-tb_j\)。通过观察我们很容易可以得出b_i是递增的，且t也是递增的。我们不妨将t当作是随i递增的一个时间。对于\(i>j\)，若当前\(a_i-tb_i>a_j-tb_j\)，即\(i\)当前不优于\(j\)，通过一段时间后总会有\(i\)优于\(j\)，因为\(b_i>b_j\)，随着t的增大，\(i\)的减少量比\(j\)多。若\(a_i-t_0b_i=a_j-t_0b_j\)，则当\(t>=t_0\)后\(i\)会一直比\(j\)优。

        现在再考虑三个决策\(i,j,k\)的情况。假设在\(t_0\)时刻\(i\)比\(j\)优，在\(t_1\)时刻\(j\)比\(k\)优，且\(t_0<t_1\)，那么j这个方案就可以舍去了，因为在\(j\)比\(k\)更优时，\(i\)已经比\(j\)更优了，且这个更优是具有传递性的，\(i\)比\(k\)优的时刻一定是\(<=t_1\)的（这个可以用下面的斜率式子说明）。

        \(a_i-tb_i>a_j-tb_j\)，可以得到\(t=\frac{a_i-a_j}{b_i-b_j}\)，即两点间斜率。这就是斜率优化的本意。

        具体实现就放在上面那个链接里了。

        加强：上面的题目有一个特殊的性质：\(b_i\)和\(t\)都是单调的。对于一个更普遍的\(f_i=max(a_ix_j+b_iy_j)\)的情况，我们就不能直接这么做了，因为\(x_i,y_i\)等都不一定是单调的。将该式变形，我们可以得到\(y_j=-\frac{a_i}{b_i}x_j+\frac{f_i}{b_i}\)，即经过点\((y_j,x_j)\)，斜率为\(-\frac{a_i}{b_i}\)的一条直线，与y轴相交于\(\frac{f_i}{b_i}\)，对于一个确定的i，直线的斜率是已知的，我们需要找的是最优的那个点\((x_j,y_j)\)。显然根据线性规划的性质，答案肯定在凸包上，我们可以选择用一棵平衡树来维护凸包，也可以选择用cdq分治来维护凸包并计算答案。具体见http://zarxdy34.is-programmer.com/posts/211567.html