Pyramid
TopCoder Custom Round
Time Limit: 0.2s, Memory Limit: 64MiB
Ели играе на компютърна игра, в която трябва да се строи нещо като Ацтекска пирамида. Играта е двуизмерна, като земята е най-долният ред на екрана. Камъни с височина 1 пиксел и различни широчини падат от небето в различни позиции (измервано от лявата страна на екрана).
Камъните падат един след друг като Ели решава за всеки от тях дали да го унищожи, или да го остави да падне. Първият камък, който бъде оставен да падне, ляга на земята и служи за основа на пирамидата. Всеки следващ, който бива оставен да падне, трябва да ляга изцяло върху предишния паднал. Например, ако последният паднал камък започва в пиксел L и свършва в пиксел R (включително), началото и краят на следващия неунищожен камък трябва да са в интервала [L, R].
Камъните, които момичето остави да паднат, се натрупват един върху друг в нещо като пирамида. Целта на играта е тя да бъде възможно най-висока.
Камъните падат един след друг като Ели решава за всеки от тях дали да го унищожи, или да го остави да падне. Първият камък, който бъде оставен да падне, ляга на земята и служи за основа на пирамидата. Всеки следващ, който бива оставен да падне, трябва да ляга изцяло върху предишния паднал. Например, ако последният паднал камък започва в пиксел L и свършва в пиксел R (включително), началото и краят на следващия неунищожен камък трябва да са в интервала [L, R].
Камъните, които момичето остави да паднат, се натрупват един върху друг в нещо като пирамида. Целта на играта е тя да бъде възможно най-висока.
Вход
На първия ред на стандартния вход ще бъде дадено едно цяло число N – колко каменни блока ще има. Всеки от следващите N реда ще съдържа по две цели числа Li и Ri – най-левия и най-десния пиксел (включително) от падащ блок. Блоковете са дадени в реда, в който падат.
Изход
На стандартния изход изведете едно цяло число – максималната височина на пирамидата (тоест колко най-много блока могат да бъдат оставени да паднат).
Ограничения
- 1 ≤ N ≤ 50
- 1 ≤ Li ≤ Ri ≤ 1,000
| Примерен Вход | Примерен Изход |
|---|---|
| 9 3 4 2 7 3 7 4 6 2 7 3 9 5 5 5 5 13 17 | 5 |
Най-добре е да унищожим първия каменен блок, тъй като е относително малък. Основата на пирамидата ще бъде вторият камък ([2, 7]). Третият също може да оставим – [3, 7] е изцяло в [2, 7]. Взимаме и [4, 6]. Следващият блок ([2, 7]) не може да бъде взет, ако последният оставен камък е [4, 6]. Забележете, че ако не бяхме взели [3, 7] и [4, 6], бихме могли да сложим [2, 7] върху другото [2, 7], но това би довело до неоптимален отговор. Последните два камъка, които можем да вземем, са [5, 5], и още веднъж [5, 5]. Така отговорът е 5: ([2, 7], [3, 7], [4, 6], [5, 5], [5, 5]).