신도시 건설

해설

각 건물은 다른 건물과 관계없이 높이를 정할 수 있다. 따라서 $i$ 번 건물에서 얻을 수 있는 가장 큰 값인 $\max(B_1,\ldots,B_{A_i})$ 를 모두 더하면 된다.

$h=2,3,\ldots,M$ 순서로 $B_h \gets \max(B_h,B_{h-1})$ 로 갱신한다. 그러면 에는 원래 수열의 처음 개 원소 중 최댓값이 저장된다. 정답은 이다.

시간 복잡도는 $O(N+M)$ , 공간 복잡도는 $O(N+M)$ 이다.

max

(

Bh

,

Bh−1

)

B_h

h

\sum_{i=1}^{N}B_{A_i}