2016年2月25日 星期四

[HOJ 200][COI 2012]SETNJA (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 200 - SETNJA

Problem Statistics
Solved Member: 3  Submission: 6  User Tried: 4
Problem:
Mirko 大大想要帶他的朋友們去一場將在 Zagreb 舉行的 "Zaz" 演唱會。他已經拿到足夠的票了,因此他現在正在他家附近散步,順便將票分給他的朋友們。

Mirko 家附近可以用一個笛卡爾坐標系來表示。當 Mirko 大大在走路的時候,他只會踩在格子點上〈即x, y座標均為整數〉。他走路時有八個方向,分別是上下左右和對角四方位。

Mirko 的每位朋友也都住在格子點上,並且他們會走到他們家附近和 Mirko 會面。Mirko 只能和朋友在格子點上會面,而且因為每個朋友都有屬於自己的懶惰程度 P,因此只能在離每位朋友家 P 步的距離碰面。

Mirko 回家之後,他記得他拜訪朋友們的順序,請你依照這個順序計算出他所需要走的步數最小值為多少。

請注意,Mirko 的起點和終點是未知的。
Input:
第一行有一個整數 N(2 ≤ N ≤ 200 000),代表 Mirko 的朋友數量。

接下來有 N 行,每行有三個整數,分別代表這位朋友家的 x, y 座標和懶惰程度 P。

這N行資訊依照 Mirko 的拜訪順序排序。
Output:
請輸出唯一一行,代表 Mirko 完成他的任務所需要走的最少步數。
Sample Input:
SAMPLE A:
3
3 10 2
8 4 2
2 5 2

SAMPLE B:
4
3 3 5
7 11 5
20 8 10
30 18 3
Sample Output:
SAMPLE A:
4

SAMPLE B:
19
HINT:
占分 30% 的測資裡,N 最大值為 200。
另外 30% 的測資,P 不會超過 10。

第一筆範例測資中,Mirko 從 (4, 8) 碰到他的第一個朋友,並在 (6, 6) 碰到第二個朋友,並在 (4, 5) 碰到他的第三個朋友。
Source:
COI 2012
Problem Setter
Nekosyndrome
Testdata:
TestTimeMemoryScore
0-13000ms262144kb
0-23000ms262144kb
13000ms262144kb10
23000ms262144kb10
33000ms262144kb10
43000ms262144kb10
53000ms262144kb10
63000ms262144kb10
73000ms262144kb10
83000ms262144kb10
93000ms262144kb10
103000ms262144kb10

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原