[問題] 程式作業加分題

看板Prob_Solve (計算數學 Problem Solving)作者 (Jimmy)時間5年前 (2018/10/26 12:17), 5年前編輯推噓5(502)
留言7則, 7人參與, 5年前最新討論串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, 5年前 , 1F
這個應該可以直接推數學解吧我猜
10/26 12:23, 1F

10/26 13:46, 5年前 , 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, 5年前 , 3F
用離散法
10/30 09:43, 3F

11/03 10:37, 5年前 , 4F
DP
11/03 10:37, 4F

11/06 07:08, 5年前 , 5F
感覺這種題目幾乎都是用DP
11/06 07:08, 5F

11/10 19:41, 5年前 , 6F
未看先猜ADA
11/10 19:41, 6F

12/19 07:31, 5年前 , 7F
Floyd warshall?
12/19 07:31, 7F
文章代碼(AID): #1RqfLTft (Prob_Solve)
討論串 (同標題文章)
文章代碼(AID): #1RqfLTft (Prob_Solve)