学习笔记 - 告别精度:从斜率优化到凸包优化

在CF上做题做多了,偶然发现那些斜率优化的题目的标签中都有一个“CHT”?

- 凸包优化


# 为什么需要凸包优化

学习稍加深入的OIer大都了解斜率优化,然而“凸包优化(CHT)”在中国鲜为人知……但是,这玩意在国外很火的样子 awa,似乎所有斜率优化的题都能用它做——反正我把它理解为斜率优化的一种实现方式

要说这俩的区别,还真的蛮大的(尽管时间复杂度都是相同的):

  • 我们所了解的斜率优化,其实是用一个包含类似斜率的表达式来判断两个转移点的优劣;把一个转移点抽象为平面直角坐标系中的一个点
  • 而凸包优化,不需要把转移式进行什么变动,非常直观地把每一个转移点看成一条直线(一个函数);

至于为什么要学这个?就是因为它好用嘛~

  1. 思路简单,无脑;
  2. 图像直观,不容易出锅;
  3. 通过某些小技巧可以使某一类题的计算过程中不涉及小数,因此完全避免精度问题;
  4. 它是李超线段树的基础算法。

# 主要思想

对于一类形如:

的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)$ 单增):

jpg1

有三个转移点,对应的直线表达式为图的左侧所示。既然是要求 max,我们不妨画出这三条直线的 max 的函数图像:

jpg2

显然是个下凸包嘛……而且我们发现 $y_2=x+2$ 根本就没在凸包上,于是就不需要这条直线(这是第一种需要删除直线的情况)

随着 $X(i)$ 向右移,也会有一些直线不再需要,这时候就可以删除掉!(这是第二种需要删除直线的情况)

gif1

这样的话,就可以单调队列来维护了。

reader们可以想一下什么时候用单调栈


# 补充

之前 “#主要思想” 中保证了 $X(i)$ 单增,如果不单调呢?

就意味着之前 (第二种需要删除直线的情况) 就不存在了,而要找到最对应的直线,复杂度就需要多加一个 $O(\log n)$——二分查找。

还有一个条件是 $K(j)$ 单增,如果不单调呢?那么就对我们维护凸包造成了困难,这时候就可以上李超树了~(平衡树再见)


# 源代码

版题:Blue Mary 开公司 (洛谷或BZOJ)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*Lucky_Glass*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const double ERR=-3.1415926*5.12723*1e7,EPS=1e-9;
const int N=1e5,M=5e4;

inline double fABS(const double &x){return x<0? -x:x;}

struct LINE{
double Ek,Eb;
LINE(){}
LINE(double ek,double eb):Ek(ek),Eb(eb){}
double Calc(const double &Dx){return Ek*Dx+Eb;}
double Cros(const LINE &ano){
if(fABS(Ek-ano.Ek)<=EPS) return ERR;
return (Eb-ano.Eb)/(ano.Ek-Ek);
}
}lin[N+3],*thi;
struct SEGTREE{
LINE *idx[M*5];
void Build(int u,int lef,int rig){
idx[u]=NULL;
if(lef==rig) return;
int mid=(lef+rig)>>1;
Build(u<<1,lef,mid);
Build(u<<1|1,mid+1,rig);
}
void Insert(int u,int lef,int rig,LINE *now){
if(!idx[u]){idx[u]=now;return;}
if(idx[u]->Calc(lef)<now->Calc(lef)+EPS && idx[u]->Calc(rig)<now->Calc(rig)+EPS){idx[u]=now;return;}
if(now->Calc(lef)+EPS>idx[u]->Calc(lef) || now->Calc(rig)+EPS>idx[u]->Calc(rig)){
int mid=(lef+rig)>>1;
if(idx[u]->Calc(mid)<now->Calc(mid)+EPS)
swap(idx[u],now);
if(idx[u]->Cros(*now)<mid+EPS) Insert(u<<1,lef,mid,now);
else Insert(u<<1|1,mid+1,rig,now);
}
}
double Query(int u,int lef,int rig,double Dx){
if(!idx[u]) return 0;
int mid=(lef+rig)>>1;
if(Dx<mid+EPS) return max(idx[u]->Calc(Dx),Query(u<<1,lef,mid,Dx));
else return max(idx[u]->Calc(Dx),Query(u<<1|1,mid+1,rig,Dx));
}
}Se;

int n;
char cmd[20];

int main(){
thi=lin;
scanf("%d",&n);
Se.Build(1,1,M);
while(n--){
scanf("%s",cmd);
if(cmd[0]=='P'){
double Dk,Db;scanf("%lf%lf",&Db,&Dk);
++thi;*thi=LINE(Dk,Db-Dk);
Se.Insert(1,1,M,thi);
}
else{
int Dx;scanf("%d",&Dx);
printf("%lld\n",(long long)floor(max(Se.Query(1,1,M,Dx)/100,0.0)));
}
}
return 0;
}

The End

Thanks for reading!

除了暴力分治以外最快乐的算法……

0%