금속 가공 공장

Yulia는 Ekaterinburg의 금속 가공 공장에서 일한다. 매달 n개의 광석 shipment가 도착하고, Yulia는 유사도에 따라 두 그룹으로 나눈다.

모든 쌍 (i, j)에 거리 d(i,j)가 있고, 부분집합 S의 disparity는

D(S) = max_{i,j in S} d(i,j)

이다 (원소가 1개 이하면 0). 두 그룹 A, B로 나눌 때 D(A)+D(B)를 최소화하라.

• 1행: n (1 ≤ n ≤ 200)
• 다음 n-1행: i행에 d(i,i+1) ... d(i,n) 순서로 정수

가능한 D(A)+D(B)의 최솟값