BOJ 17526 - Star Trek

April 10, 2023

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 구현체와 함께라면 쉽게 풀 수 있다.

You may also enjoy