[問題] 程式作業加分題

[aaaa11140 (Jimmy)]

這是一個程式作業的加分題，
對於平面上兩點A,B，d(A,B)表示從A到B的最短時間，
而移動的方式包括knight moving的8種以及上下左右一次一格，
knight moving一次需時2秒，上下左右則是1秒。

e.g.

d((0,0),(2,2))=3

題目給定N個點，求每個點與其他點的最短時間和，意即對於第i的點xi，求Σd(xi,xj),1<=j<=N

N最大為10^5，時間限制2秒，所以不可能用兩個loop找任意兩點時間，希望跟大家討論。


現在的進度是d(A,B)可以用O(1)的時間得知，問題卡在找所有任意兩點的方法。

-----
Sent from JPTT on my Samsung SM-N960F.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.173.191
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1540527453.A.A77.html
→ alan23273850: 這個應該可以直接推數學解吧我猜
推 s89162504: 從x*x到(x+1)*(x+1)應該不難推吧
推 ckc1ark: 最後要回答的是一個數字還是N個數字?
N個數字


[m10/26 18:30
推 JameC: 可以把公式拆開來吧？拆開來後就可以一個點一個點算了       10/26 19:06
※ 編輯: aaaa11140 (114.136.173.191), 10/26/2018 20:04:28
※ 編輯: aaaa11140 (114.136.173.191), 10/26/2018 20:05:44
※ 編輯: aaaa11140 (114.136.173.191), 10/26/2018 20:09:36
→ bigload1234: 用離散法
推 ken32293355: DP
推 kyrie77: 感覺這種題目幾乎都是用DP
推 rrkqq: 未看先猜ADA
推 plsmaop: Floyd warshall?