P6898 [ICPC 2014 WF] Metal Processing Plant

Yulia 在叶卡捷琳堡的一家金属加工厂工作。该工厂处理从乌拉尔山脉开采的矿石，从中提取黄铜矿、铂金和黄金等贵金属。每个月，工厂会收到 $n$ 批未加工的矿石。Yulia 需要根据相似性将这些矿石分成两组。然后，每组被送往工厂的两个矿石加工建筑之一。 为了进行这种划分，Yulia 首先为每对矿石 $1 \le i \le n$ 和 $1 \le j \le n$ 计算一个数值距离 $d(i, j)$，距离越小，矿石 $i$ 和 $j$ 越相似。对于矿石的一个子集 $S \subseteq \{ 1, \ldots , n\} $，她定义 $S$ 的差异度 $D$ 为子集中一对矿石之间的最大距离，即， $$ D(S) = \max _{i, j \in S} d(i, j). $$ 然后，Yulia 将矿石划分为两个子集 $A$ 和 $B$，使得它们的差异度之和 $D(A) + D(B)$ 最小。你的任务是帮助她找到这种划分。

输入由一个单一的测试用例组成。第一行包含一个整数 $n$ ($1 \le n \le 200$)，表示矿石的数量。接下来的 $n - 1$ 行包含距离 $d(i,j)$。这些行的第 $i$ 行包含 $n - i$ 个整数，该行的第 $j$ 个整数给出 $d(i, i+j)$ 的值。距离是对称的，因此 $d(j, i) = d(i, j)$，且矿石自身的距离为 $0$。所有距离都是 $0$ 到 $10^9$（含）之间的整数。

输出将矿石划分为两组的差异度之和的最小可能值。

时间限制：2000 毫秒，内存限制：1048576 kB。 国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2014。 题面翻译由 ChatGPT-4o 提供。