1621 . 張貼海報
TopCoder
Tags
Description
台北市有都市規劃了！所有建築物在東區地帶蓋成一排，而且沒有間距（沒有巷弄了！？）。它們形成一個極長的建築物群，從北向南延伸。
市長已經決定將建築物群的東方牆面貼滿海報（遮陽光？）。市長思考如何以最低數量的海報覆蓋整個建築物群的東面。海報都是長方形的。它們不能重疊，但可以互相接觸。每一張海報要完全貼在建築物的牆壁上。
Input Format
第一行的標準輸入包含一個整數 n (1<=n<=250,000)，指建築物群的數目。
每一行包含兩個整數 di和 wi (1<=di ,wi<=1,000,000,000)，由一個空格隔開，表示第i個建築物的長度與高度。
Output Format
輸出最少所需要的海報數。
Sample Input 1
5
1 2
1 3
2 2
2 5
1 4
1 2
1 3
2 2
2 5
1 4
Sample Output 1
4
Hints
Problem Source
原TIOJ1621 / Source: POI XV Postering
problem setter: 乃牛
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |