斜率优化再理解

· · 个人记录

dp_i = max_{j<i}(f_j = (dp_j - x_j*x_i)) j优于k的条件(k < j) dp_j - x_j*x_i >= dp_k - x_k*x_i

\frac{dp_j - dp_k}{x_j-x_k}>=x_i

若现有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无用可以弹出