JAG Practice Contest for ACM-ICPC Asia Regional 2015 K Optimal Tournament 题解

首先可以发现每一场比赛都对应着一段连续区间，可以从下往上归纳。

如果存在一个节点的两个儿子是两个相离的区间，则可以通过移动某一段使答案更优，这个证明比较简单。

然后就可以dp了,\(f_{i,j,z}\)表示区间\([i,j]\)深度为\(z\)的答案。

\[f_{i,j,z}=\min\{f_{i,k,z-1}+f_{k+1,j,z-1}+a_j-a_k\} \]

很容易猜到它满足决策单调性。

一点证明：

容易发现若存在两个区间\(seg1,seg2\)满足\(seg1\subset seg2\),则\(Ans(seg1\cup T)-Ans(seg1)\leq Ans(seg2\cup T)-Ans(seg2)\)，通俗地来说：区间元素越多加进来同样的元素答案增加的越多，这个可以感谢理解一下，很显然是对的。

这样就可以证明\(f\)满足四边形不等式了：\(f_{b,c}+f_{a,d}\geq f_{a,c}+f_{b,d}\Leftrightarrow f_{b,d}-f_{b,c}\leq f_{a,d}-f_{a,c},(a<b<c<d)\) 。

好像很多四边形不等式都可以这样感性证明，当然打表就更稳妥了。