PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 程式作業加分題

看板Prob_Solve (計算數學 Problem Solving)作者 (Jimmy)時間6年前 (2018/10/26 12:17), 6年前編輯推噓5(5推 0噓 2→)
留言7則, 7人參與, 6年前最新討論串1/2 (看更多)
這是一個程式作業的加分題， 對於平面上兩點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
→
10/26 12:23, 6年前 , 1F
這個應該可以直接推數學解吧我猜
10/26 12:23, 1F
推
10/26 13:46, 6年前 , 2F
從x*x到(x+1)*(x+1)應該不難推吧
10/26 13:46, 2F
推 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
→
10/30 09:43, 6年前 , 3F
用離散法
10/30 09:43, 3F
推
11/03 10:37, 6年前 , 4F
DP
11/03 10:37, 4F
推
11/06 07:08, 6年前 , 5F
感覺這種題目幾乎都是用DP
11/06 07:08, 5F
推
11/10 19:41, 6年前 , 6F
未看先猜ADA
11/10 19:41, 6F
推
12/19 07:31, 6年前 , 7F
Floyd warshall?
12/19 07:31, 7F
‣ 更多 aaaa11140 的文章
文章代碼(AID): #1RqfLTft (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 aaaa11140 的文章
文章代碼(AID): #1RqfLTft (Prob_Solve)