Link Sub: http://www.spoj.com/PTIT/problems/P157PROE/
Người Gửi: Sai
- Problem:
Một cửa hàng đá quý và trang sức nhận thấy rằng các viên kim cương sẽ càng hấp dẫn với người mua hơn nếu trọng lượng càng nhỏ và độ trong suốt càng cao. Cho trước N viên kim cương. Giả sử trọng lượng viên kim cương thứ i được biểu diễn bởi một số thực wi từ 0.0 đến 10.0. Còn độ trong suốt thì cho bởi số thực ci, cũng trong khoảng từ 0.0 đến 10.0.Hãy tìm ra độ dài dãy con dài nhất có thể trong đó trọng lượng thì tăng dần còn độ trong suốt thì giảm dần. Ví dụ, với 6 viên kim cương có các giá trị biểu diễn như sau:
1.5 9.0
2.0 2.0
2.5 6.0
3.0 5.0
4.0 2.0
10.0 5.5
thì dãy con dài nhất có độ dài bằng 4, bao gồm các viên kim cương thứ 1, 3, 4, và 5.
Input
Dòng đầu tiên ghi số bộ test (không quá 100).
Mỗi bộ test bắt đầu bằng số N là số viên kim cương (1<=N<=200). Tiếp theo là N dòng, mỗi dòng ghi lần lượt 2 số thực wi và ci (đều trong khoảng từ 0.0 đến 10.0)
Output
Với mỗi bộ test, ghi ra trên một dòng giá trị độ dài của dãy con dài nhất có thể.
Example:
Với mỗi bộ test, ghi ra trên một dòng giá trị độ dài của dãy con dài nhất có thể.
Input
3
2
1.0 1.0
1.5 0.0
3
1.0 1.0
1.0 1.0
1.0 1.0
6
1.5 9.0
2.0 2.0
2.5 6.0
3.0 5.0
4.0 2.0
10.0 5.5
Output:
2
1
4