#1717. Metal Processing Plant
Metal Processing Plant
Metal Processing Plant
题目描述
Problem G Metal Processing Plant Time Limit: 4 seconds Yulia works for a metal processing plant in Eka- terinburg. 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 un- processed ore. Yulia needs to partition these ship- ments into two groups based on their similarity. Then, each group is sent to one of two ore pro- cessing buildings of the plant. To perform this partitioning, Yulia first calculates a numeric distance d(i, j) for each pair of ship- ments 1 i n and 1 j n, where the Picture from Wikimedia Commons smaller the distance, the more similar the ship- ments 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, D(S) = max i,j2S d(i, j). Yulia then partitions the shipments into two subsets A and B in such a way that the sum of their dispar- ities 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. Sample Input 1 Sample Output 1 5 4 4 5 0 2 1 3 7 2 0 4 ACM-ICPC World Finals 2014 Problem G: Metal Processing Plant 13 Sample Input 2 Sample Output 2 7 15 1 10 5 5 5 5 5 10 5 5 5 100 100 5 5 10 5 5 98 99 3 ACM-ICPC World Finals 2014 Problem G: Metal Processing Plant 14
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5
4 5 0 2
1 3 7
2 0
4
4
样例 2
7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3
15