MDOLLS - Nested Dolls

no tags 

"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

hide comments
rishabh_jiit: 2019-03-11 14:57:46

Those who are unable to understand the question. Read the question from here.
https://journeywithdp.blogspot.com/2018/06/spoj-mdolls-nested-dolls.html

egoista_: 2018-05-21 07:48:48

Great Problem. Learnt Dilworth's Algorithm and implementd using largest non-increasing subsequence.

shashankpathak: 2018-03-20 07:41:54

How to approach this problem using Dilsworth theorem??
Thanks in advance

biradarganesh: 2018-01-02 06:28:49

Can someone please explain the problem? I've been trying for an hour to understand the problem, but I'm unable to even understand what they're asking us to do!

anmolx123: 2017-07-24 22:10:03

How is the third Test case giving output 3??

amiri: 2017-06-22 08:47:34

There is an beautiful O(n log n) solution using LIS

Last edit: 2017-06-22 14:15:00
candide: 2017-05-01 19:27:21

Solved in C and Python with binary search. Didn't try maximum bipartite matching.

Last edit: 2017-05-01 21:16:26
César Giglio Badoino: 2016-04-03 05:23:01

@naruto09 2 dolls

naruto09: 2016-01-16 09:03:44

i/o :
1
6
72 85 61 86 55 85 43 63 65 39 44 30
can someone please tell output of this test case..?

Last edit: 2016-01-16 09:03:56
sughosh v kaushik: 2015-08-15 14:03:09

greedy is good but with binary search this time :)

Last edit: 2015-08-15 14:20:02

Added by:~!(*(@*!@^&
Date:2009-02-24
Time limit:0.156s-0.259s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Nordic 2007