d087: Q-6-23. 直升機抓寶 (@@)(*)(105 高中全國賽)
Tags : DP
Accepted rate : 5人/7人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-04-25 22:27

Content

小智的學校在天空之城,他每天開直升機上學,現在他想要規劃一條路徑以便在從家裡到學校的路上可以抓到最多的寶貝,請你寫個程式幫助他。

我們將學校與他家之間所有的位置劃分成 N*N 的格子,每個格子以坐標(x,y)表示,

其中 x 代表水平距離,y 代表高度,而小智家的坐標在(0,0)的位置,學校在(N-1,N-1)的位置,由於他的父母不准他上學途中貪玩繞路,直升機被設定成每次只能向前或向上一格,也就是說,只能從(x,y)到(x+1,y)或(x,y+1),當然,他也不可以超過x<N且Y<N的範圍,否則會無法到達學校。

小智到學校的路途上一共有 N 隻寶貝,每隻寶貝可以補獲的範圍是某特定高度而水平座標在某連續區間的格子。明確的說,對於寶貝 P(i), 0≦ i <N,要捕抓到 P(i),小智必須經過下列座標之一:{(x,y)| S(i)≦x≦T(i) and y=i},其中所有的S(i)與 T(i)都已經透過抓寶雷達得到資料了。

上圖是一個 N=5 的例子,藍色區塊顯示可以捕抓到寶貝的地方,請注意,每一個寶貝 都是在一個水平連續區間。紅線所顯示的路徑是一條合乎規定的路徑,因為他每一步 都只有向右或向上,沿這一條路徑可以捕抓到四隻寶貝,是所有可能路徑中可以捕抓 到寶貝數最多的。

Input

第一行是座標範圍的 N,接下來 N 行,每一行有兩個整數 S(i)與 T(i),

依序是 i=0,1,…N-1,其中 0≦S(i)≦T(i)<N<2.5e5。​​

Output

最多可能抓到的寶貝數。

Sample Input
// 1
5
1 3
0 1
3 4
0 0
2 3
// 2
2
1 1
0 0
Sample Output
// 1
4
// 2
1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」