CDQ 优化斜率优化 DP

__ryp__ · 2024-06-24 19:33:07 · 个人记录

有的题，横坐标和所切的斜率均不单调，比如 P4655 Building Bridges，这时候我们可以用 CDQ 分治来把朴素的 O(n^2) 优化到 O(n\log n)。

具体方法比较简单。CDQ 分治所考虑的核心就是左区间对右区间的贡献。怎么转化成为朴素的斜率优化 DP 呢？左边区间的横坐标要单调，右边区间所切的斜率要单调。

这样，我们就先按照切的斜率排序，然后计算左边对右边的贡献，然后按照横坐标排序。