806 . 觀光行程

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

sayu

User's AC Ratio

100.0% (11/11)

Submission's AC Ratio

70.6% (12/17)

Tags

apcsc apcsc-dp

Description

本題改編自 2021 年 1 月 APCS 考古題。

豆島是一個觀光導遊兼顧問，主要負責為旅行社安排行程。為了讓行程看起來緊湊有效率，豆導希望無論如何都只往東北方走，以避免看起來像在往回頭路的方向走。

如果將當前位置座標定在 (0,0)，且正 y 軸方向為北方。給定 N 個位於座標 (x,y) 上的景點，豆導希望規劃一條路線使得經過的景點 x 座標總是不比前一個小，y 座標也不比前一個小。

想請問你，基於 N 座城市位置和豆導的堅持下，一個行程最多能包含多少景點。

Input Format

輸入第一行是一整數 N，代表城市數量。

接下來 N 行是兩個空白分隔的整數 x,y，代表景點的座標。

對於 20% 的輸入，保證 1≤n,x,y≤100。
對於 30% 的輸入，保證 1≤n≤1000，1≤x,y≤107。
對於 50% 的輸入，保證 1≤n≤200000，1≤x,y≤107。

輸入保證沒有兩個景點位置完全相同。

Output Format

輸出一行一個整數，代表最多可以拜訪的景點。

Sample Input 1

3
1 1
2 7
3 1

Sample Output 1

2

Sample Input 2

5
1 2
2 2
2 3
3 3
3 4

Sample Output 2

5

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~8 1≤n,x,y≤100 20
3 0~12 1≤n≤1000,1≤x,y≤107 30
4 0~24 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2 3 4
1 2000 524288 65536 1 2 3 4
2 2000 524288 65536 2 3 4
3 2000 524288 65536 2 3 4
4 2000 524288 65536 2 3 4
5 2000 524288 65536 2 3 4
6 2000 524288 65536 2 3 4
7 2000 524288 65536 2 3 4
8 2000 524288 65536 2 3 4
9 2000 524288 65536 3 4
10 2000 524288 65536 3 4
11 2000 524288 65536 3 4
12 2000 524288 65536 3 4
13 2000 524288 65536 4
14 2000 524288 65536 4
15 2000 524288 65536 4
16 2000 524288 65536 4
17 2000 524288 65536 4
18 2000 524288 65536 4
19 2000 524288 65536 4
20 2000 524288 65536 4
21 2000 524288 65536 4
22 2000 524288 65536 4
23 2000 524288 65536 4
24 2000 524288 65536 4
Submit
Back to Top