Xếp gạch
Xem PDF
Điểm:
500 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho \(N\) viên gạch hình chữ nhật có kích thước là \(a_i, b_i, h_i\) lần lượt là chiều dài, chiều rộng, chiều cao của viên gạch thứ \(i\).
Tìm cách xếp các khối gạch thành 1 tháp. Sao cho các cạnh của các viên gạch song song với nhau và hình chữ nhật ở phía trên nằm trọn trong hình chữ nhật phía dưới.
Viên gạch thứ \(j\) có thể nằm trên viên gạch thứ \(i\) khi \(a_i>a_j\) và \(b_i>b_j\)
Tìm số viên gạch tối đa có thể chồng lên nhau và chiều cao tối đa của tháp.
Input
- Dòng đầu tiên chứa một số nguyên dương \(N\) (\(n\le 5000\)) là số viên gạch
- \(N\) dòng tiếp theo mỗi dòng chứa 3 số \(a_i, b_i, h_i\).
Output
- Gồm 2 số \(x,y\) lần lượt là số viên gạch tối đa trong 1 tháp và chiều cao tối đa của tháp dựng tự các viên gạch
Example
Test 1
Input
10
9 7 1
10 4 8
8 5 5
7 4 10
7 4 8
5 1 9
2 1 10
3 2 4
5 4 5
10 3 2 Output
5 30
Bình luận
test 43 bị làm saooooooooooooooooooooooooo ấy mãi không ac test đó huhu
Để làm đc bài này,các bạn hãy xem or làm qua bài tập sắp xếp lịch họp trc nhé. Sau đây mình xin chia sẻ cách làm như sau:
Đây là code của mình, khuyến khích các bạn hãy làm 3 bài QHĐ trên trc khi đọc code của mình
Làm sao làm bài này vậy? Cho em xin hint với
hmmmm
Sao không có giới hạn \(a_i\) , \(b_i\) , \(h_i\) ạ ?
cách xếp tháp để được nhiều được nhiều viên nhất khác cách xếp để được chiều cao cao nhất nhé các bạn @@