BOJ 17526 - Star Trek
CHT 연습 문제이다.
$dp[i]=$ $i$ 번째 행성으로 이동할 수 있는 가장 빠른 시간이라고 하자.
$dp[1]=0$ 이고, 정답은 $dp[N]$ 이다.
$$
\begin{aligned}
dp[i]=
Min_{j=1 \dots i-1}\{ dp[j]+p_j+(d_i-d_j)s_j\}\\
=Min_{j=1 \dots i-1}\{s_jd_i+dp[j]+p_j-d_js_j\}
\end{aligned}
$$
이므로, $s_j$ 가 직선의 기울기이다.
$N \le 100,000$ 이므로 추가적인 최적화가 필요없을 것 같다.
LineContainer 구현체와 함께라면 쉽게 풀 수 있다.
Comments