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
Để 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
-
1
VoBaThongL921
4:29 p.m. 12 Tháng 10, 2021
←
đã chỉnh sửa
→
-
0
longkold00
4:31 p.m. 12 Tháng 10, 2021
-
1
VoBaThongL921
4:38 p.m. 12 Tháng 10, 2021
-
1
longkold00
4:43 p.m. 12 Tháng 10, 2021
←
đã chỉnh sửa
→
-
0
VoBaThongL921
3:53 p.m. 12 Tháng 10, 2021
-
1
longkold00
3:56 p.m. 12 Tháng 10, 2021
-
1
longkold00
3:55 p.m. 12 Tháng 10, 2021
5 bình luận nữaDamn thanks anh nhiều nha :)) struct hay thế :>
hì,cùng quê bạn a, em tính thi chuyên tin hửm :v
Dạ:) mà non quá"(
Cứ cố gắng thoi em, được tiếp cận sớm với lập trình thì đã là 1 lợi thế rùi đó, a đến khi vào đh r mới đc tiếp cận nên cũng chẳng theo nổi bọn e lun 🙁
em chưa học quy hoạch động nên để vài tháng nữa thầy em dạy đã:( sád
cơ mà em học ở trường nèo thía :v, a hơi tò mò á
:v hồi c2 bọn a còn chưa biết pascal là gì :<