一种另类的斜率优化?
查看原帖
一种另类的斜率优化?
554746
yiming564楼主2024/9/13 12:02

萌新第一次学斜率优化,看题解实在没有看懂,但是自己口胡了一个同样维护上凸包的算法,感觉和正常的斜率优化不太一样,不过效率倒是不错。

对于 fi=fj+A(i)B(j)+C(i)+D(j)f_i = f_j + A(i)B(j) + C(i) + D(j),整理得:

fiC(i)=B(j)A(i)+fj+D(j)y=fiC(i)k=B(j)b=fj+D(j)x=A(i)\begin{aligned} f_i - C(i) &= B(j)A(i) + f_j + D(j) \\ y &= f_i - C(i) \\ k &= B(j) \\ b &= f_j + D(j) \\ x &= A(i) \end{aligned}

这样,原问题就被转化为了 类似 P3194,这种方法理解简单,至少比题解区的做法简单。

我想知道这种方法是否是斜率优化的另一种形式,还是说这是一种新的算法?

2024/9/13 12:02
加载中...