[BalticOI 2004] Sequence (Day1)
\(f_{i,x}\) 表示考虑前 \(i\) 个位置，当前放了 \(x\)。转移式如下：
\[f_{i,x} = |a_i - x| + f_{i - 1,x}
\]
考虑建坐标系，有点 $(x,f_{i,x})。然后它就相当于给当前的函数加上个 \(y=|a_i-x|\)。
\[f_{i,x} = \min\{f_{i,x},f_{i,x-1}\}
\]
注意到，我们每次加的是上凸函数，所以 \(f_i\) 也是上凸函数。因此想要实现上面这个转移，只需把斜率 >0 的地方抹平即可。
于是，上述过程可以用一个堆维护函数拐点。