HoTaru.HRC's blog

By HoTaru.HRC, 9 years ago,

Dolls

Divorce is the most famous doll collector in the word,he has a huge amount of dolls. You know? Among all sizes of dolls, the most smallest doll can be covered by the second smallest doll,etc. One day,he wants to use a way called absolute contain, and make the left dolls least. Here, absolute contain means no one more doll can be contained in another. you can have different dolls with dolls contained. For example, 4 dolls are made up of 4 3 2 2 dolls is legal. A doll has a width w and a height h. if 2 dolls which w1<w2 and h1<h2 then the first doll can be contained in the second doll. Help Divorce please! Tell him the least dolls after absolute contain.

[Input] a number m(1-40000),shows the number of dolls,and the following 2*m integers w1,h1,w2,h2..etc,are the width and length of m dolls,wi&hi are the width and height of the ith doll.(wi,hi 1-10000)

[Output] A number shows the least number of dolls.

E.G.1

Dolls.in 4 20 30 10 10 30 20 40 50 dolls.out 2

Dolls.in 3 1 2 1 2 1 2 dolls.out 3

• +3

 » 9 years ago, # |   0 Asking for help :) I don't know how to solve T T
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 I think that the problem you mentioned was in the problem set of NCPC 2007 (Nordic contest), and it can be solved using DP (specifically, LIS). In this contest, it's called "Nested Dolls" and it's the problem G. See the explanation in the links below:Good luck.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 Sorry for my bad traslation. Thanks for your information. Really useful.:)
 » 9 years ago, # |   0 http://poj.org/problem?id=3636 The same problem.
 » 9 years ago, # |   0 DP & greedy may be possible methods.