前言
显然啊,这道题应该用斜率优化来做,但是,又很显然,我不是那种喜欢推式子(雾,到最后还是推了啊)写 DP 的人,那么,刚好我学了模拟退火,那么就来试一试模拟退火过了这道题。
解题思路
我们已经知道了什么?
- 如果用模拟退火的话,至少要 20 20 20 次,最低温 1 e − 18 1e-18 1e−18 才能过这道题,那么,卡死了时间复杂度为 O ( 20 × log 0.998 8.7336244541484716157205240174672 e − 22 × O ( 单次计算 ) ) O(20\times{\log_{0.998}^{8.7336244541484716157205240174672e-22}}\times O(\text{单次计算})) O(20×log0.9988.7336244541484716157205240174672e−22×O(单次计算)),其值近似等于 O ( 20 × 16139 × O ( 单次修改 ) ) O(20\times 16139\times O(\text{单次修改})) O(20×16139×O(单次修改)),等于 O ( 326380 × O ( U p d a t e ) ) O(326380\times O(Update)) O(326380×O(Update)),算上常数,差不多就是 O ( 3.5 × 1 0 5 × O ( U p d a t e ) ) O(3.5\times 10^5\times O(Update)) O(3.5×105×O(Update)),显然, O ( U p d a t e ) ≤ 860 O(Update)\le 860 O(Update)≤860,也就是说,我们应该在 O ( n ) O(\sqrt n) O(n) 及以下的时间复杂度内完成计算。
- 很显然,选择锯木厂得位置的话,选在某两棵树的位置是最优的。
- 如果没有锯木厂的话,那么运送的花费为 ( ( s 1 × w 1 ) + ( s 2 × w 2 ) + ( s 3 × w 3 ) + … + ( s n × w n ) ) \left((s_1\times w_1)+(s_2\times w_2)+(s_3\times w_3)+…+(s_n\times w_n)\right) ((s1×w1)+(s2×w2)+(s3×w3)+…+(sn×wn)),其中 s i s_i si 表示第 i i i 个点到山脚下锯木厂的距离。显然, w 1 … w n w_1 … w_n w1…wn 是不变的,那么很显然只能改变 s 1 … s n s_1 … s_n s1…sn 的值,那么我们转化一种记录距离的方法,用 s i s_i si 表示第 1 1 1 棵树到第 i i i 棵树的距离,那么我们就会有第 j j j 棵树到第 i i i 棵树的距离为 s i − s j s_i-s_j si−sj,即第 1 1 1 棵树到第 i i i 棵树的距离减去第 1 1 1 棵树到第 j j j 棵树的距离。这时,我们就可以很方便地计算出每一个点到山脚下锯木厂的距离。假设我们把第一个锯木厂设置在位置 l l l 上,第二个锯木厂设置在位置 r r r 上,那么,我们可以得到,前 l l l 棵树到 l l l 的距离为前 l l l 棵树到达山脚下锯木厂的距离减去 l l l 到山脚下锯木厂的距离,即为 s i − s l s_i-s_l si−sl。
- 因此,我们可以得到前 l l l 棵树的花费为 ( s i − s l ) × w i + … + ( s l − s l ) × w l (s_i-s_l)\times w_i+…+(s_l-s_{l})\times w_l (si−sl)×wi+…+(sl−sl)×wl,展开后得到 : s i × w i − s l × w i + … + s l × w l − s l × w l s_i\times w_i-s_l\times w_i+…+s_l\times w_l-s_l\times w_l si×wi−sl×wi+…+sl×wl−sl×wl = = = s i × w i + … + s l × w i − s l × ( w i + … + w l ) s_i\times w_i+…+s_l\times w_i-s_l\times(w_i+…+w_l) si×wi+…+sl×wi−sl×(wi+…+wl),设原本前 i i i 棵树的花费为 C i C_i Ci,前 i i i 棵树的重量之和为 W i W_i Wi,那么,新得到的前 l l l 棵树的的花费为 C l − s l × W l C_l-s_l\times W_l Cl−sl×Wl;
- 因此,我们可以得到中间的 r − l r-l r−l 棵树的花费为 ( s i − s r ) × w i + … + ( s r − s r ) × w r (s_i-s_r)\times w_i+…+(s_r-s_r)\times w_r (si−sr)×wi+…+(sr−sr)×wr,展开后得到: s i × w i − s r × w i + … + s r × w r − s r × w r s_i\times w_i-s_r\times w_i+…+s_r\times w_r-s_r\times w_r si×wi−sr×wi+…+sr×wr−sr×wr = = = s i × w i + … + s r × w r − s r × ( w i + … + w r ) s_i\times w_i+…+s_r\times w_r-s_r\times(w_i+…+w_r) si×wi+…+sr×wr−sr×(wi+…+wr),设原本前 i i i 棵树的花费为 C i C_i Ci,前 i i i 棵树的重量之和为 W i W_i Wi,那么,新的到的中间 r − l r-l r−l 棵树的花费为 C r − C l − s r × ( W r − W l ) C_r-C_l-s_r\times(W_r-W_l) Cr−Cl−sr×(Wr−Wl);
- 剩下的部分则花费不变,总的新花费为 C n − s r × ( W r − W l ) − s l × W l C_n-s_r\times(W_r-W_l)-s_l\times W_l Cn−sr×(Wr−Wl)−sl×Wl
好了,现在我们已经可以做到 O ( n ) O(n) O(n) 预处理, O ( 1 ) O(1) O(1) 单次计算新的值了,那么总时间复杂度即为 O ( 3.5 × 1 0 5 ) O(3.5\times 10^5) O(3.5×105),好像还是比斜率优化慢了不少啊,不过毕竟是骗分用的嘛。