금속 가공 공장
시간 제한4초메모리 제한128 MB
n개 화물을 두 그룹으로 나누어 각 그룹 안에서 가장 먼 두 화물 사이 거리의 합을 최소화합니다.
문제
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)의 최솟값