作者aaaa11140 (Jimmy)
看板Prob_Solve
标题[问题] 程式作业加分题
时间Fri Oct 26 12:17:31 2018
这是一个程式作业的加分题，
对於平面上两点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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1540527453.A.A77.html
1F：→ alan23273850: 这个应该可以直接推数学解吧我猜10/26 12:23
2F：推 s89162504: 从x*x到(x+1)*(x+1)应该不难推吧10/26 13:46
推 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
3F：→ bigload1234: 用离散法 10/30 09:43
4F：推 ken32293355: DP 11/03 10:37
5F：推 kyrie77: 感觉这种题目几乎都是用DP 11/06 07:08
6F：推 rrkqq: 未看先猜ADA 11/10 19:41
7F：推 plsmaop: Floyd warshall? 12/19 07:31