MDOLLS - Nested Dolls

"Dilworth" có một bộ sưu tập các con búp bê Nga.  Búp bê với chiều rộng w1 
và chiều cao h1 sẽ nằm trong được con lật đật chiều rộng w2 và chiều cao h2
nếu w1 < w2 và h1 < h2. 

Tính số lớp búp bê bao nhau ít nhất mà có thể tạo ra được từ các búp bê ban đầu.
Image and video hosting by TinyPic

Input

Dòng đầu là số test,  1 ≤ t ≤ 20. Mỗi test bắt đầu là số nguyên m, 1 ≤ m ≤ 20000, 
số lượng búp bê ban đầu. Dòng tiếp theo là 2m số nguyên w1, h1,w2, h2,
... ,wm, hm, là chiều rộng và chiều cao của con búp bê thứ i, 1 ≤ wi, hi ≤ 10000.

SAMPLE INPUT
4
3
20 30 40 50 30 40
4
20 30 10 10 30 20 40 50
3
10 30 20 20 30 10
4
10 10 20 30 40 50 39 51

Output

 
Ghi số lớp búp bê bao nhau ít nhất có thể trên một dòng cho từng test.

SAMPLE OUTPUT
1
2
3
2

Được gửi lên bởi:~!(*(@*!@^&
Ngày:2009-02-24
Thời gian chạy:0.156s-0.259s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Nordic 2007

hide comments
2019-05-29 13:26:03
tại sao test 1 lại ra 1 ấy
2018-04-19 14:08:15
Tại sao dùng lower_bound thì sao mà dùng upper_bound thì lại đúng?
2018-03-15 11:43:12
._. nghe lời mấy bác "<=" em mất mịa 1 đấm
làm theo đề
frostpixel aka.How 2 AC

Last edit: 2018-03-15 11:48:45
2017-12-07 11:42:08
w1<=w2 và h1<=h2 nha !
2017-12-02 18:56:44


Last edit: 2017-12-02 18:57:46
2017-03-22 15:42:05
Bác nào thông cho e phát coi
2017-02-13 09:12:47
con búp bê rồi con lật đật ???
2017-01-04 04:09:50
không biết làm sao mà cứ báo làm sai hoài! nản wa
2016-05-23 03:34:22 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/179/mdolls-spoj/

Last edit: 2016-10-01 06:01:34
2016-04-16 09:55:01
yeah mừng quá, cả tiếng mới xong
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.