백준 8571 - Apteka (C++)

문제 문제 링크 BOJ 8571 - Apteka 문제 요약 $N$명의 $C_i$값이 주어진다. 자리를 바꿀 때마다 문제에 정의된 데로 비용이 발생할 때, 맨 앞으로 가는 최소 비용을 구해보자.

제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N ≤ 10^6$ $1 ≤ C_i ≤ 10^9$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화 (convex hull trick) 풀이 우선 문제를 다음과 같이 이해하면 편하다. "$Hansel$의 위치가 $0$ 번 인덱스이고, $1, 2, ...

N$번 인덱스 사람들의 $C_i$가 주어진다. 자리 스왑마다 $Hansel$과 $i$가 떨어진 거리 * $C_i$ 의 비용이 발생 한다고 할 때 $Hansel$이 $N$번째 자리에 도달.....