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
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 @@
-
0
algorit
6:17 p.m. 24 Tháng 8, 2020
5 bình luận nữa😆