Problems
To perform this partitioning, Yulia first calculates a numeric distance d(i, j) for each pair of shipments 1 ≤ i ≤ n and 1 ≤ j ≤ n, where the smaller the distance, the more similar the shipments i and j are. For a subset S ⊆ {1, . . . , 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,
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.
Input
The input consists of a single test case. The first line contains an integer n (1 ≤ n ≤ 200) indicating the number of shipments. The following n - 1 lines contain the distances d(i, j). The ith of these lines contains n - i integers and the jth 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 109 (inclusive).
Output
Display the minimum possible sum of disparities for partitioning the shipments into two groups.
Example #1
5
4 5 0 2
1 3 7
2 0
4
4
Example #2
7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3
15
You must sign in to write code.