P157PROE spoj PTIT – ROUND 7E – Kim cương

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P157PROE/

1. Đề bài P157PROE spoj

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:

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:

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
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

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

2. Hướng dẫn P157PROE spoj PTIT

– Đây là bài toán QHĐ tìm dãy con tăng đơn điệu dài nhất.

– gọi F[i] là độ dài dãy con thỏa mãn đề bài có phần tử cuối cùng là i

– khởi tạo F[0]=0, W[0]:= âm vô cực, C[0]:= dương vô cực, F[i]=0.

-Nếu W[i]>W[j] và C[i]<C[j] thì F[i]:=max(F[i],F[j]+1); (i=1..n, j=0..i-1).

– Đáp án = Max(F[i]) (i=1..n).

3. code tham khảo P157PROE spoj PTIT

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *