[ICPC2014 WF] Metal Processing Plant

**题目描述** 尤利娅在叶卡捷琳堡的一家金属加工厂工作。该工厂在乌拉尔山脉提取矿石中的铜、铂和金。工厂每月收到 $n$ 批未经处理的矿石。尤利娅需要对这些货物进行分割为两组。然后它们会分别被送到工厂的两个冶矿塔。 首先，尤利娅对每对货物 $i,j(1\leq i,j\leq n)$ 给出一个$d_{i,j}$，对于子集 $S$，$D(S)$ 定义为 $\max\limits_{(i,j\in S)}\{d_{(i,j)}\}$。 然后，尤利娅将货物分成 $A$ 和 $B$ 两部分，使 $D(A)+D(B)$ 最小。请你帮助她找到划分方法。 **输入格式** 输入包括多组数据。 对于每组测试数据： 第一行包含一个整数 $n(1\leq n\leq 200)$，表示发货数量。接下来 $n-1$ 行每行有 $n-i$ 个数，第 $j$ 个数表示 $d_{i,i+j}$。且 $d_{j,i}=d_{i,j},d_{i,i}=0$。 **输入格式** 对于每组测试数据，输出 $D(A)+D(B)$ 的最小值。

Yulia works for a metal processing plant in Ekaterinburg. This plant processes ores mined in the Ural mountains, extracting precious metals such as chalcopyrite, platinum and gold from the ores. Every month the plant receives $n$ shipments of unprocessed ore. Yulia needs to partition these shipments into two groups based on their similarity. Then, each group is sent to one of two ore processing buildings of the plant. To perform this partitioning, Yulia first calculates a numeric distance $d(i, j)$ for each pair of shipments $1 \le i \le n$ and $1 \le j \le n$, where the smaller the distance, the more similar the shipments $i$ and $j$ are. For a subset $S \subseteq \{ 1, \ldots , n\} $ of shipments, she then defines the disparity $D$ of $S$ as the maximum distance between a pair of shipments in the subset, that is, $$ D(S) = \max _{i, j \in S} d(i, j). $$ Yulia then partitions the shipments into two subsets $A$ and $B$ in such a way that the sum of their disparities $D(A) + D(B)$ is minimized. Your task is to help her find this partitioning.

The input consists of a single test case. The first line contains an integer $n$ ($1 \le n \le 200$) indicating the number of shipments. The following $n - 1$ lines contain the distances $d(i,j)$. The $i^{th}$ of these lines contains $n - i$ integers and the $j^{th}$ integer of that line gives the value of $d(i, i+j)$. The distances are symmetric, so $d(j, i) = d(i, j)$, and the distance of a shipment to itself is $0$. All distances are integers between $0$ and $10^9$ (inclusive).

Display the minimum possible sum of disparities for partitioning the shipments into two groups.

5
4 5 0 2
1 3 7
2 0
4

4

7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3

15

Time limit: 2000 ms, Memory limit: 1048576 kB. International Collegiate Programming Contest (ACM-ICPC) World Finals 2014