Xếp Chồng Hộp Chiều Cao Tối Đa
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ chiếc hộp chữ nhật, hộp thứ $i$ có chiều dài $l_i$, chiều rộng $w_i$ và chiều cao $h_i$ (không được phép xoay hộp). Hộp $A$ có thể đặt lên trên hộp $B$ nếu và chỉ nếu $l_A < l_B$ và $w_A < w_B$. Hãy chọn một số hộp và xếp chồng lên nhau sao cho tổng chiều cao đạt được là lớn nhất.
Dữ liệu vào
- Dòng đầu: số nguyên dương $N$ $(1 \le N \le 2000)$.
- $N$ dòng tiếp theo: mỗi dòng gồm ba số nguyên dương $l_i, w_i, h_i$ $(1 \le l_i, w_i, h_i \le 10^9)$.
Dữ liệu ra
- In ra tổng chiều cao lớn nhất có thể.
Ví dụ
| Input | Output |
|---|---|
| 4\n4 6 7\n1 2 3\n4 5 6\n10 12 32 | 42 |
| 3\n1 2 10\n2 1 10\n2 2 5 | 10 |
Giới hạn
- $1 \le N \le 2000$
- $1 \le l_i, w_i, h_i \le 10^9$
- Thời gian: 1 giây
- Bộ nhớ: 256 MB
Community Discussion