HoTaru.HRC's blog

By HoTaru.HRC, 9 years ago, In English

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

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Asking for help :)

I don't know how to solve T T

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DP & greedy may be possible methods.