땅값 흥정
플래티넘 I의견: 0
\(N\)개의 직사각형 토지를 사려고 한다. \(i\)번째 토지의 너비는 \(w_i\), 높이는 \(h_i\)이다. 토지들을 여러 묶음으로 나누어 사는데, 한 묶음의 가격은 그 묶음에 속한 토지들의 (최대 너비) \(\times\) (최대 높이)이다.
토지를 적절히 묶어 총 비용을 최소로 하려고 한다. (어떤 토지 \(a\)가 다른 토지 \(b\)에 대해 \(w_a \le w_b\)이고 \(h_a \le h_b\)이면, \(a\)는 항상 \(b\)와 같은 묶음에 넣어도 추가 비용이 들지 않는다. 즉 다른 토지에 완전히 포함되는 토지는 무시할 수 있다.)
최소 총 비용을 구하여라.
\(O(N^2)\) DP는 통과할 수 없다.
\(1 \le N \le 50{,}000\)
\(1 \le w_i, h_i \le 10^6\)
첫 줄에 토지의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각 토지의 너비 \(w_i\)와 높이 \(h_i\)가 주어진다.
모든 토지를 사는 데 드는 최소 총 비용을 출력한다.
4
1 4
3 1
2 2
2 3
11토지 (2,2)는 (2,3)에 포함되어 무시된다. 남은 토지를 너비 오름차순으로 정렬하면 (1,4),(2,3),(3,1). 묶음 {(1,4),(2,3)}=2×4=8, 묶음 {(3,1)}=3×1=3. 합 11이 최소이다.
1
5 5
25토지가 하나뿐이면 그 토지 자체가 한 묶음이며 비용은 \(5\times5=25\)이다.
riseoj 작성
출처 Original
평가 및 의견
땅값 흥정
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
땅값 흥정