MDOLLS - Nested Dolls

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mdolls


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

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:psetter
Ngày:2009-02-24
Thời gian chạy:1s
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
2015-05-31 11:36:49 Life Like Bike
Đề max hack não nhưng được cái chả hiểu đề nói gì :))

Last edit: 2015-05-31 13:16:30
2015-05-14 06:20:29 Prismatic
Sort tăng theo W, W bằng nhau thì H giảm, rồi dùng LIS trên H, đề đúng rồi, ko có dấu =


Last edit: 2015-05-29 09:39:24
2015-04-25 10:47:29 lucky++
Mô phật cuối cùng cũng AC, đề đúng.
2015-02-05 18:35:31 Con Bò Huyền Thoại
http://dangminhtien.name.vn/blog/2015/02/05/mdolls-spoj-nested-dolls-bup-nga/
2014-12-18 14:37:23 Lihn
đậu phụ ông Bee Sociu AC rồi thì cũng đừng lừa tình ng` ta thế chứ chấm mất xừ 1 phát rồi >''<
2014-10-25 12:06:45 ■■‡[ND] Bee Sociu■■‡
Đề Troll :)) Ai WA coi lại cái chỗ h1 < h2, w1 < w2 :)) thêm dấu bằng nữa nhé :))
2014-08-04 15:29:17 Tây Cuồng
bài này hay... :(
2014-06-22 13:07:31 Thcs Ðặng Chánh Kỷ
chỉ khác mỗi dấu = mà sai cả bài
2014-06-22 13:02:40 Thcs Ðặng Chánh Kỷ
cuối cùng cũng ac, bài gai thật
2014-06-22 12:33:05 Thcs Ðặng Chánh Kỷ
bài này khó ac thật
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.