Loading...
N개의 도시가 일렬로 나열되어 있다. 각 도시 i에는 비용 $c_i$가 부여되어 있다.
도시 1에서 출발하여 도시 N까지 이동해야 한다. 도시 i에서 도시 j(i < j)로 직접 이동할 때 드는 비용은 $(c_i + c_j) \times (j - i)$이다. 도시를 건너뛰며 이동할 수 있으며, 이동 경로에 상관없이 도시 1에서 도시 N까지 도달하는 데 필요한 총 이동 비용의 최솟값을 구하라.
이 문제는 이동 비용을 수식으로 전개하면 $i \cdot c_i - j \cdot c_j + j \cdot c_i - i \cdot c_j$ 꼴로 나타낼 수 있어, 볼록 껍질 트릭(Convex Hull Trick)이나 리차오 트리(Li Chao Tree) 같은 특수한 자료구조를 사용하여 $O(N \log N)$에 해결할 수 있다.
첫째 줄에 도시의 개수 N이 주어진다.
둘째 줄에 N개의 정수 $c_1, c_2, \ldots, c_N$이 공백으로 구분되어 주어진다.
도시 1에서 도시 N까지 이동하는 총 비용의 최솟값을 출력하라.
3
1 2 3
8
4
1 10 2 3
14