레이팅 미적용설명
농부 존(Farmer John)이 농장 울타리의 구멍을 고치는 것을 잊어버려서, N마리 (1 <= N <= 1,000)의 소들이 탈출하여 난동을 부리고 있다! 소가 울타리 밖에 있는 매 분마다 1달러어치의 피해가 발생한다. FJ는 각 소를 찾아가 소를 진정시키고 피해를 멈추게 하는 고삐를 채워야 한다.
다행히 소들은 농장 밖 도로의 직선을 따라 서로 다른 위치에 있다. FJ는 자신이 출발하는 문(위치 0)을 기준으로 각 소 i의 위치 P_i (-500,000 <= P_i <= 500,000, P_i != 0)를 알고 있다.
FJ는 1분에 거리 1단위씩 이동하며, 고삐는 즉시 채울 수 있다. 총 피해 비용을 최소화하려면 FJ가 소들을 어떤 순서로 방문해야 하는지 알아내고, 이때의 최소 총 피해 비용을 계산하시오.
(이 문제는 USACO 2013년 3월 대회 실버 3번 및 골드 1번 문제로 동일하게 출제되었다.)
제약
입력 형식
첫째 줄: 소의 수 N.
둘째 줄부터 N+1번째 줄까지: i+1번째 줄에 정수 P_i가 주어진다.
출력 형식
최소 총 피해 비용.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
cowrun.in · 출력을 쓸 파일 cowrun.out예제 1
입력
4
-2
-12
3
7출력
50설명
Output details: The optimal visit order is -2, 3, 7, -12, giving cumulative damage 2 + 7 + 11 + 30 = 50.
문제 정보
태그