萌新第一次学斜率优化,看题解实在没有看懂,但是自己口胡了一个同样维护上凸包的算法,感觉和正常的斜率优化不太一样,不过效率倒是不错。
对于 fi=fj+A(i)B(j)+C(i)+D(j)f_i = f_j + A(i)B(j) + C(i) + D(j)fi=fj+A(i)B(j)+C(i)+D(j),整理得:
这样,原问题就被转化为了 类似 P3194,这种方法理解简单,至少比题解区的做法简单。
我想知道这种方法是否是斜率优化的另一种形式,还是说这是一种新的算法?