[BOJ] 2300번: 기지국

https://www.acmicpc.net/problem/2300

D[i]를 0번째부터 i번째 건물까지 연결하는 설치비용의 최솟값이라고 둡니다. i번째 건물을 포함하는 기지국이 j번째 건물까지 포함한다고 가정할 경우 설치 비용은 max(j~i번째 건물 높이 중 최대 높이*2, i번째 건물과 j번째 건물 사이의 가로축 거리) + D[j-1]로 계산이 가능합니다. 그러면 j = 0~i까지 대입을 했을 때 D[i]를 갱신할 수 있게 됩니다. 이를 가지고 D[i]를 i번만에 구할 수 있고, 최종적으로 D[0]부터 쌓아올라가면 O(N^2)으로 답을 구할 수 있게 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/2300.cpp