c230: 松鼠旅行
標籤 : TIOJ 1419
通過比率 : 89% (8 人 / 9 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-08-07 19:07

內容 :

飛天桑妮是一隻運動神經很好的松鼠,她很喜歡在樹木間移動,尤其最愛從高處一躍
而下,享受滑翔的快感。她所居住的森林裡有 N 棵樹木,已知每棵樹 ti 的位
置 (xi, yi) 和高度 hi。桑妮的家 t1 位於 (0, 0),而桑妮的奶奶家 tN 位於 (10000, 10000)
的位置。這個週末她要去奶奶家,因而尋求你的協助。
從家裡前往奶奶家的旅程可定義為由 K (1 < K) 棵相異樹木構成的序列
p = [p(1) = 1, p(2), …, p(K) = N]。
由於桑妮想要快點到奶奶家,所以旅程後段的樹木不能比前段的樹木離桑妮家還近,也就
是 d(t1, tp(i+1)) 不小於 d(t1, tp(i)),其中 d(ti, tj) 表示兩棵樹 ti 和 tj 的直線距離。當桑妮從一棵較
高的樹 tp(i) 跳到下一棵樹 tp(i+1) 時,如果是由高到低,她就能使出滑翔絕技,享受樂趣。
高度差越大,樂趣就越大,因此我們可以把樂趣值定為 max{0, hp(i) - hp(i+1)}。她希望這段
旅程中可以享受到最大的樂趣,因此想請你幫忙寫一個程式,計算所有可能的旅程中,最
大的樂趣值為多少。

輸入說明

第一列有一個正整數 N (N <= 100,000),代表森林中的樹木數。接下來的 N 列,每一
列有3個正整數 xi、yi (1 <= xi, yi <= 10,000) 和 hi (1 <= hi <= 100,000),彼此間以一個空白隔開,
代表第i 棵樹ti 在位置(xi, yi),且該樹高度為hi

輸出說明

請輸出所有合理旅程中,最大的樂趣值。

範例輸入
5
3000 1000 50
8000 7000 100
0 0 100
3000 5000 300
10000 10000 150
範例輸出
200
測資資訊:
記憶體限制: 16 MB
不公開 測資點#0 (100%): 0.1s , <1M
提示 :
標籤:
TIOJ 1419
出處:
2016台北市資訊學科能力複賽 [編輯: k034006 (Sine Wu) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」