백준 17526 - Star Trek (C++)

문제 문제 링크 BOJ 17526 - Star Trek 문제 요약 1에서 $n$으로 이동하려고 한다. 문제에 정의된 비용을 따를 때, 가장 최소의 비용으로 이동하는 경우를 구해보자.

제한 TL : $1$ sec, ML : $512$ MB $3 ≤ n ≤ 100,000$ $1 ≤ s ≤ 100,000$ $0 ≤ p ≤ 1,000,000,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화(convex hull trick) 누적 합(prefix sum) 풀이 임의의 지점으로 가는 데엔 결국 그 이전 지점들 중에 어디에서 환승하냐가 관건이다. 두 지점 간 거리를 빠르게 계산하기 위해 누적 합( $p[]$ )을 이용하자.

이후, 간단하게 점화식을 만들어 볼 수 있다. $dp[i]$ : $.....