CF321E Ciel and Gondolas
\[dp_{k,i}=\min\{dp_{k-1,j}+w(j+1,i)\} \\ w(l,r)= \sum_{l \le i < j \le r} u(i,j)
\]
\(w(x,y)\) 满足四边形不等式，证明：
Submission 352461026
P4767 [IOI 2000] 邮局 加强版
\[dp_{k,i}=\min\{dp_{k-1,j}+w(j+1,i)\} \\ w(l,r)= \sum_{i=l}^r |x_i-x_{\lfloor\frac{l+r}{2}\rfloor}|
\]
注意到 \(w(l,r)\) 有递推 \(w(l,r)=w(l,r-1)+x_r-x_{\lfloor\frac{l+r}{2}\rfloor}\)：
-
\([l,r-1]\) 区间长度为奇数，添加 \(r\) 后中位数还是 \(\lfloor\frac{l+r}{2}\rfloor\)
-
\([l,r-1]\) 区间长度为偶数，添加 \(r\) 后中位数位置 \(+1\)，但由于原 \(\text{mid}\) 在中间两个数之间任意取，所以位置 \(+1\) 不影响前面的答案
\(w\) 满足四边形不等式，证明：
\(w(l,r+1)=w(l,r)+x_{r+1}-x_{\lfloor\frac{l+r+1}{2}\rfloor} \cdots \textcircled{1}\)
\(w(l-1,r+1)=w(l-1,r)+x_r-x_{\lfloor\frac{l+r}{2}\rfloor} \cdots \textcircled{2}\)
\(\textcircled{1} - \textcircled{2}, w(l,r+1)+w(l-1,r)=w(l,r)+w(l-1,r+1)+\underline{x_{\lfloor\frac{l+r}{2}\rfloor}-x_{\lfloor\frac{l+r+1}{2}\rfloor}, \le 0}\)
\(w(l,r+1)+w(l-1,r) \le w(l,r)+w(l-1,r+1)\)，推广即得结论