【开坑】

斜率优化学习笔记

Zarxdy34 posted @ 2017年11月30日 15:09 in ACM with tags 斜率优化 , 62 阅读

        经典问题: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


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Back to Top