斜率优化DP
斜率优化dp
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133955843
考虑变成点对 ，则
令 ，得 ，即
我们希望 尽量小，也就是截距尽可能小，即下图红色部分
对于点对，我们维护凸壳
可以发现，在第一个切的地方我们可以取截距最小
维护凸壳采用的是单调队列，我们维护两点之间斜率递增
如果新加入的点会使斜率递减，则把队尾的点pop掉
然后我们就可以二分 / 决策单调性了
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2026-07-09
一些动态规划的优化算法：斜率优化、四边形不等式、Slope Trick、wqs二分
一些动态规划的优化算法：斜率优化、四边形不等式、Slope Trick、wqs二分 斜率优化 考虑我们求解的问题可以简化为： fi=min(fj−j×ai)f_i=\min(f_j-j\times a_i) fi=min(fj−j×ai) 令 fi=b,fj=y,ai=kf_i=b,f_j=y,a_i=kfi=b,fj=y,ai=k，则： b=y−kx⇒y=kx+bb=y-kx\\ \Rightarrow y = kx + b b=y−kx⇒y=kx+b 其中 (x,y)(x,y)(x,y) 是本来就有的点（而且有很多个，均为备选项），bbb 为我们要求的东西，我们希望 b...
2023-12-16
李超线段树维护斜率DP：P4655
李超线段树维护斜率dp：P4655 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135036474 https://www.luogu.com.cn/problem/P4655 这东西长得就很像斜率优化的东西，但是不能用朴素斜率优化，因为横坐标不满足递增。 但我们可以直接用李超线段树维护即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454...
2023-10-20
wqs二分+斜率优化：1019T4 / P9338
wqs二分+斜率优化：1019T4 / P9338 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133955885 https://www.luogu.com.cn/problem/P9338 考虑暴力前 iii 个分 jjj 段 fi,k=fj−1,k−1+gj,if_{i,k}=f_{j-1,k-1}+g_{j,i}fi,k=fj−1,k−1+gj,i ， O(n3)O(n^3)O(n3) 然后划分段数，段数显然越多越优，那么就上wqs二分， O...