飛天桑妮是一隻運動神經很好的松鼠,她很喜歡在樹木間移動,尤其最愛從高處一躍
而下,享受滑翔的快感。她所居住的森林裡有 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
ID | User | Problem | Subject | Hit | Post Date |
38452 | qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) | c230 | 197 | 2023-11-24 19:54 | |
31557 | 20060705sean (pneumonoultrami...) | c230 | 459 | 2022-08-07 11:36 |