신호 중계 최소 비용
다이아몬드 V의견: 0
일렬로 놓인 \(N\)개의 중계소가 번호 \(1\)부터 \(N\)까지 매겨져 있다. 각 중계소 \(i\)는 두 정수 특성값 \(a_i\)와 \(b_i\)를 가진다.
신호는 항상 \(1\)번 중계소에서 출발한다. 어떤 중계소 \(j\)에서 더 큰 번호의 중계소 \(i\)(\(j < i\))로 신호를 한 번 보내는 데 드는 비용은 \(a_i \cdot b_j\)이다. 신호가 \(1\)번 중계소에서 시작하여 (한 번 이상 거쳐서) \(N\)번 중계소에 도달할 때, 총 전송 비용의 최솟값을 구하여라.
정확히는 \(dp_1 = 0\), \(dp_i = \min_{1 \le j < i}\big(dp_j + a_i \cdot b_j\big)\)이며 \(dp_N\)을 구하는 문제이다.
\(2 \le N \le 200{,}000\)
\(-10^6 \le a_i, b_i \le 10^6\)
첫 줄에 정수 \(N\)이 주어진다.
둘째 줄에 \(a_1, \dots, a_N\)이, 셋째 줄에 \(b_1, \dots, b_N\)이 주어진다.
\(dp_N\), 즉 \(N\)번 중계소까지의 최소 총 전송 비용을 출력한다.
3
0 2 3
1 -4 5
-10\(dp_1=0\). \(dp_2 = dp_1 + a_2 b_1 = 0 + 2\cdot1 = 2\). \(dp_3 = \min(dp_1 + a_3 b_1,\ dp_2 + a_3 b_2) = \min(0+3\cdot1,\ 2+3\cdot(-4)) = \min(3, -10) = -10\).
2
5 5
3 7
15중계소가 둘뿐이다. \(dp_2 = dp_1 + a_2 b_1 = 0 + 5\cdot3 = 15\).
riseoj 작성
출처 Original
평가 및 의견
신호 중계 최소 비용
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
신호 중계 최소 비용