关于斜率优化的 slope 函数
  • 板块灌水区
  • 楼主Hanx16Kira
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/11/10 20:43
  • 上次更新2023/10/27 03:29:10
查看原帖
关于斜率优化的 slope 函数
345225
Hanx16Kira楼主2022/11/10 20:43

斜率优化 DP 里面有用到一个 slope 来求斜率,然后可能出现两个坐标的横坐标相同导致算斜率 ΔyΔx\dfrac{\Delta y}{\Delta x} 中的 Δx=0\Delta x = 0,然后开心 RE。

可不可以对 Δx\Delta x 加上一个极小值 ϵ\epsilon,这样就使得横坐标不会为 00 了。

P3648 [APIO2014] 序列分割 试了一下,发现这种做法好像可行,我取的 ϵ=1e15\epsilon = 1e-15

提交记录

所以有大佬来说一下这种方法是否是可行的,或者不可行在哪里?

2022/11/10 20:43
加载中...