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

最近更新 : 2020-09-23 21:33

Content

小智的學校在天空之城,他每天開直升機上學,現在他想要規劃一條路徑以便在從家

裡到學校的路上可以抓到最多的寶貝,請你寫個程式幫助他。

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

其中 x 代表水平距離,y 代表高度,而小智家的坐標在(0,0)的位置,學校在(N-1,N1)的位置,由於他的父母不准他上學途中貪玩繞路,直升機被設定成每次只能向前或

向上一格,也就是說,如果從(x,y)到(x+1,y)或(x,y+1),當然,他也不可以超過

x

小智到學校的路途上一共有 N 隻寶貝,每隻寶貝可以補獲的範圍是某特定高度而水平

座標在某連續區間的格子。明確的說,對於寶貝 P(i), 0≦ i

小智必須經過下列座標之一:{(x,y)| S(i)≦x≦T(i) and y=i},其中所有的

S(i)與 T(i)都已經透過抓寶雷達得到資料了。

Input

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

依序是 i=0,1,…N-1,其中 0≦S(i)≦T(i)

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
沒有發現任何「解題報告」