UVA1703 Metal Processing Plant
题目描述
尤利娅在叶卡捷琳堡的一家金属加工厂工作。该工厂在乌拉尔山脉提取矿石中的铜、铂和金。工厂每月收到 $n$ 批未经处理的矿石。尤利娅需要对这些货物分割为两组。然后它们会分别被送到工厂的两个冶矿塔。
首先，尤利娅对每对货物 $i,j(1\leq i,j\leq n)$，给出一个 $d(i,j)$，对于子集 $S$，$D(S)$ 定义为 $d(i,j)_{max}(i,j\in S)$。
然后，尤利娅将货物分成 $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)$ 的最小值。
**输入样例：**
```
5
4 5 0 2
1 3 7
2 0
4
7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3
```
**输出样例：**
```
4
15
```