再论斜率优化前言问题斜率优化另一种问题后记前言早在2024年9月3日本蒟蒻就发布了一篇斜率优化的讲解然而我那个时候过于菜了理解不是很深刻于是今天重写一篇。问题见洛谷P10979至于那个削弱版的绿题就是费用提前计算我之前讲得挺明白了这里不再讲了。再那个题中我们使用了前缀和和费用提前计算优化DP转移式如下。d p i m i n ( d p j s u m t i × ( s u m c i − s u m c j ) s × ( s u m c n − s u m c j ) ) dp_i min(dp_j sumt_i \times (sumc_i - sumc_j) s \times (sumc_n - sumc_j))dpimin(dpjsumti×(sumci−sumcj)s×(sumcn−sumcj))其中s u m c sumcsumc和s u m t sumtsumt就是c cc和t tt的前缀和其余变量如题中所述d p i dp_idpi就是完成前i ii个任务的最小花费j jj是枚举的。我们要枚举j jj就得n 2 n^2n2过不了。考虑怎么不枚举j jj。在线段树优化DP的时候我们都是把和j jj有关的挪到一边这是有道理的因为这么做就可以把i ii和j jj拆开方便上手法维护。化一化式子得到d p j − ( s u m t i s ) × s u m c j d p i − s u m c i × s u m t i − s u m c n × s dp_j - (sumt_i s) \times sumc_j dp_i - sumc_i \times sumt_i - sumc_n \times sdpj−(sumtis)×sumcjdpi−sumci×sumti−sumcn×s上线段树的想法彻底破灭了左边还有i ii你发现含i ii的项和含j jj的项相乘了但是只有一项这个就要使用斜率优化了。斜率优化然后你继续瞪眼发现这个像直线的方程你要右面尽可能小就是将d p j dp_jdpj和s u m c j sumc_jsumcj带入这条斜率为s u m t i s sumt_i ssumtis的直线让截距最小防止你不会截距指直线和y轴交点到原点的距离为了方便我们统一钦定s u m c j sumc_jsumcj为x轴d p j dp_jdpj为y轴。然后怎么让截距最小呢可以让这条直线从负无穷的位置移上来这里复用一下两年前的老图。发现碰到的第一个点就是最小转移点。这个有性质如图。只有黄色的点能碰到也就是一个下凸包这个凸包可以单调队列维护。维护出来了之后我们只需要找到最后一条斜率小于s u m t i s sumt_i ssumtis的线段的右端点就行了。但是最坏情况下所有点都在凸包中我们扫一遍还是O(n)的。怎么办考虑斜率是s u m t i s sumt_i ssumtis随着i ii增加肯定是递增的。所以可以放进单调队列里斜率小就弹掉队头就是最佳转移点时间复杂度O(n)。#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN300010;intn,s;intc[N],t[N],sumc[N],sumt[N];intdp[N];intq[N],head1,tail1;signedmain(){cinns;for(inti1;in;i){cint[i]c[i];sumt[i]sumt[i-1]t[i];sumc[i]sumc[i-1]c[i];}dp[1]0;q[1]0;for(inti1;in;i){intkssumt[i];//斜率//计算前两个点的斜率,为(dp[q[head1]] - dp[q[head]]) / (sumc[q[head1]] - sumc[q[head]]),斜率k弹出while(headtail(dp[q[head1]]-dp[q[head]])(sumc[q[head1]]-sumc[q[head]])*k){head;}//更新dp值,我们已经维护出了最优转移点,式子套上来就行dp[i]dp[q[head]]-(k*sumc[q[head]])(sumc[i]*sumt[i])(sumc[n]*s);//i和tail的斜率 (dp[i] - dp[q[tail]]) / (sumc[i] - sumc[q[tail]])//tail和tail-1的斜率 (dp[q[tail]] - dp[q[tail-1]]) / (sumc[q[tail]] - sumc[q[tail-1]])while(headtail(dp[i]-dp[q[tail]])*(sumc[q[tail]]-sumc[q[tail-1]])(dp[q[tail]]-dp[q[tail-1]])*(sumc[i]-sumc[q[tail]])){tail--;}//插入iq[tail]i;}coutdp[n]\n;return0;}另一种问题t i t_iti可以为负话说为啥用时还能是负的?我们的斜率不仅失去了单调递增的性质而且还可以是负的。照常维护下凸包维护出的是这样的绿色的是之前没有的。发现斜率还是单调的我们判定最佳转移点的方式不变只是我们不能直接弹掉队头之后可能还有用。直接二分就好了多一个log时间复杂度可以接受。代码如下#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN300010;intn,s;intc[N],t[N],sumc[N],sumt[N];intdp[N];intq[N],tail1;signedmain(){cinns;for(inti1;in;i){cint[i]c[i];sumt[i]sumt[i-1]t[i];sumc[i]sumc[i-1]c[i];}dp[1]0;q[1]0;for(inti1;in;i){intkssumt[i];//斜率//我们规定一下,二分的是斜率k的线段的左端点,这样1就是答案了intl1,rtail,mid,res-1;while(lrtail!1){mid(lr)1;inth1q[mid],h2q[mid1];//左右端点//(dp[h2] - dp[h1]) / (sumc[h2] - sumc[h1]) kif((dp[h2]-dp[h1])k*(sumc[h2]-sumc[h1])){resmid;lmid1;}else{rmid-1;}}if(res-1)res1;//就一个点特判一下elseres;//res为q的下标,我们将其还原为原序列的下标resq[res];//更新dp值,我们已经维护出了最优转移点,式子套上来就行dp[i]dp[res]-(k*sumc[res])(sumc[i]*sumt[i])(sumc[n]*s);//i和tail的斜率 (dp[i] - dp[q[tail]]) / (sumc[i] - sumc[q[tail]])//tail和tail-1的斜率 (dp[q[tail]] - dp[q[tail-1]]) / (sumc[q[tail]] - sumc[q[tail-1]])while(tail1(dp[i]-dp[q[tail]])*(sumc[q[tail]]-sumc[q[tail-1]])(dp[q[tail]]-dp[q[tail-1]])*(sumc[i]-sumc[q[tail]])){tail--;}//插入iq[tail]i;}coutdp[n]\n;return0;}后记可以发现dp问题中想暴力很重要一眼看不出用什么那就化式子化完之后就能看出用线段树之类的数据结构还是斜率优化了用slope trick之类的也说不定本文作者是蒟蒻如有错误请各位神犇指点森林古猿出品必属精品请认准CSDN森林古猿1
