레이팅 미적용농부 존이 농장 울타리의 구멍을 고치는 것을 잊어버려서, N마리의 소 (1 <= N <= 1,000)가 탈출하여 난동을 부리고 있다! 소 한 마리가 울타리 밖에 있는 1분마다 1달러어치의 피해가 발생한다. 농부 존은 각 소를 방문하여 소를 진정시키고 피해를 멈추게 하는 고삐를 채워야 한다.
다행히 소들은 농장 밖 도로의 직선을 따라 서로 다른 위치에 있다. 농부 존은 자신이 출발하는 문(위치 0)을 기준으로 각 소 i의 위치 P_i (-500,000 <= P_i <= 500,000, P_i != 0)를 알고 있다.
농부 존은 분당 거리 1단위로 이동하며 고삐는 즉시 채울 수 있다. 총피해 비용을 최소화하기 위해 농부 존이 소들을 방문해야 하는 순서를 정하고, 이때의 최소 총피해 비용을 계산하시오.
문제 제공: Chris Tzamos, 2006
첫째 줄: 소의 수 N.
둘째 줄부터 N+1번째 줄까지: i+1번째 줄에 정수 P_i가 주어진다.
첫째 줄: 최소 총피해 비용.
cowrun.in · 출력을 쓸 파일 cowrun.out4
-2
-12
3
750Input details: Four cows placed in positions: -2, -12, 3, and 7.
Output details: The optimal visit order is -2, 3, 7, -12. FJ arrives at position -2 in 2 minutes for a total of 2 dollars in damage for that cow.
He then travels to position 3 (distance: 5) where the cumulative damage is 2 + 5 = 7 dollars for that cow.
He spends 4 more minutes to get to 7 at a cost of 7 + 4 = 11 dollars for that cow.
Finally, he spends 19 minutes to go to -12 with a cost of 11 + 19 = 30 dollars.
The total damage is 2 + 7 + 11 + 30 = 50 dollars.