P4360 [CEOI2004] 锯木厂选址
令 \(f_i\) 表示仅在 \(i\) 位置修建一个锯木厂的最小费用，\(dis_i\) 表示从山脚到 \(i\) 位置的距离，\(sum_i\) 表示从山顶到 \(i\) 位置的木材重量和，可以直接预处理出来。
那么第二个锯木厂修建在位置 \(i\) 的费用就是 \(\min\{f_j-dis_i\times(sum_i-sum_j)|j<i\}\)。
考虑两个转移点 \(j<k\)，若 \(j\) 对于当前位置 \(i\) 更优，那么：
\[f_j-dis_i\times(sum_i-sum_j)<f_k-dis_i\times(sum_i-sum_k)
\]
\[f_j-f_k<dis_i\times(sum_k-sum_j)
\]
\[\frac{f_k-f_j}{sum_k-sum_j}>-dis_i
\]
维护 \((sum,f)\) 的下凸包。