백준 - 땅따먹기(6171)

문제

 

먼저 $w_i \geqslant w_j, h_i \geqslant h_j$ 인 모든 $(i,j)$ 쌍에 대해서 $j$번 직사각형을 제거할 수 있다.

이를 통해 $i<j \rightarrow w_i \leqslant w_j, i<j \rightarrow h_i \geqslant h_j$ 를 만족하도록 ${w_k}$와 ${h_k}$를 재정렬 했다고 하자.

 

그러면 $O(N^2)$ dp로 문제를 풀 수 있다.

• $\text{dp}[i]$ : 1~i 까지의 직사각형들만 사용해서 문제를 풀 때의 최소 비용
• $\text{dp}[0] = 0$
• $\text{dp}[i] = \min_{0 \leqslant j < i} \left[ \text{dp}[j] + w_i \cdot h_{j+1} \right] \quad \text{with} \quad 1 \leqslant i \leqslant N$

 

이제 CHT를 이용해서 $O(N)$ 으로 문제를 풀면 된다.