在CF上做题做多了,偶然发现那些斜率优化的题目的标签中都有一个“CHT”?
- 凸包优化
# 为什么需要凸包优化
学习稍加深入的OIer大都了解斜率优化,然而“凸包优化(CHT)”在中国鲜为人知……但是,这玩意在国外很火的样子 awa,似乎所有斜率优化的题都能用它做——反正我把它理解为斜率优化的一种实现方式。
要说这俩的区别,还真的蛮大的(尽管时间复杂度都是相同的):
- 我们所了解的斜率优化,其实是用一个包含类似斜率的表达式来判断两个转移点的优劣;把一个转移点抽象为平面直角坐标系中的一个点。
- 而凸包优化,不需要把转移式进行什么变动,非常直观地把每一个转移点看成一条直线(一个函数);
至于为什么要学这个?就是因为它好用嘛~
- 思路简单,无脑;
- 图像直观,不容易出锅;
- 通过某些小技巧可以使某一类题的计算过程中不涉及小数,因此完全避免精度问题;
- 它是李超线段树的基础算法。
# 主要思想
对于一类形如:
的DP式子(其中 $K(j),B(j)$ 是与转移点 $j$ 相关的式子,$X(i),A(i)$ 是与当前要计算的dp值 $i$ 相关的式子),括号内的 $K(j)X(i)+B(j)$ 可以理解为一个直线的表达式:
要计算通过 $j$ 转移得到的 $i$ 的 DP 值,就把 $x=X(i)$ 代入上边的表达式再加上 $A(i)$ 就可以了。那么就是(假设是要求 max,且 $K(j)$ 单增、$X(i)$ 单增):
有三个转移点,对应的直线表达式为图的左侧所示。既然是要求 max,我们不妨画出这三条直线的 max 的函数图像:
显然是个下凸包嘛……而且我们发现 $y_2=x+2$ 根本就没在凸包上,于是就不需要这条直线!(这是第一种需要删除直线的情况)
随着 $X(i)$ 向右移,也会有一些直线不再需要,这时候就可以删除掉!(这是第二种需要删除直线的情况)
这样的话,就可以单调队列来维护了。
reader们可以想一下什么时候用单调栈
# 补充
之前 “#主要思想” 中保证了 $X(i)$ 单增,如果不单调呢?
就意味着之前 (第二种需要删除直线的情况) 就不存在了,而要找到最对应的直线,复杂度就需要多加一个 $O(\log n)$——二分查找。
还有一个条件是 $K(j)$ 单增,如果不单调呢?那么就对我们维护凸包造成了困难,这时候就可以上李超树了~(平衡树再见)
# 源代码
版题:Blue Mary 开公司 (洛谷或BZOJ)
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
除了暴力分治以外最快乐的算法……