专栏文章

斜率优化再理解

llzyzs
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqhu5po
此快照首次捕获于
2025/12/04 05:02
3 个月前
此快照最后确认于
2025/12/04 05:02
3 个月前
查看原文
dpi=maxj<i(fj=(dpj−xj∗xi))dp_i = max_{j<i}(f_j = (dp_j - x_j*x_i))
j优于k的条件(k<j)j优于k的条件(k < j)
dpj−xj∗xi>=dpk−xk∗xidp_j - x_j*x_i >= dp_k - x_k*x_i

dpj−dpkxj−xk>=xi\frac{dp_j - dp_k}{x_j-x_k}>=x_i

若现有3点i,j,k(xi<xj<xk)若现有3点i,j,k(x_i<x_j<x_k)
k_2 = k_{i,j}\\ k_3 = k_{j,k}\\ k_3 > k_1 >k_2$$
k > k_3 > k_1 > k_2\rarr f_i>f_j>f_k\
k_3 > k > k_1 > k_2\rarr f_i>f_k>f_j\
k_3 > k_1 > k > k_2\rarr f_k>f_i>f_j\
k_3 > k_1 > k_2 > k\rarr f_k>f_j>f_i\
所以j无用可以弹出 所以j无用可以弹出

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...