由于大多数的DP问题,我尝试并找到一种减低和平衡的关系。 也就是说,我可以把问题的规模缩小到每一步(如分裂和qu,但通常会把问题分开,而只是消除一小部分)。 在这个问题上(与许多其他人一样),我们可以简单地指出: 第一点在<代码>i各点,或指t。

缩略语: 让我说X ={x₁,x₂, ......,x_{/sub>}, 并注明减少的X} ={x_n, x, ...,x_{k>/sub>>>>。}

So the observation is that either x₁ is one of the i points, or it isn t. Let s call our i-set finding function MSD(i,X_k) (minimum sum of distances). We can express that cut-away observation as follows:

MSD(i,X_k) = Either MSD(i-1,X_k-1) U {x₁} or MSD(i,X_k-1)

我们可以将“要么要么要么”部分正式化,具体做法是采用简单的方式检查其中两种选择中哪一种:我们通过X套,计算距离,并检查实际规模较小。 我们当时注意到,这一检查时间为ki。 由于我们将通过<条码>k各点和绕过一套大小(<条码>i)各点的最低距离。

We make two simple observations regarding base cases:

MSD(i,X_i) = X_i
MSD(0,X_n) = {}

The first is that when looking for i points in a set of size i we obviously just take the whole set.
The second is that when looking for no points in a set, we return the empty set. This inductively ensures that MSD returns sets of size i (it s true for the case where i=0 and by induction is true according to our definition of MSD above).

That s it. That will find the appropriate set. Runtime complexity is upper bounded by O(ik * step) where step is our O(ik) check from above. This is because MSD will be run on parameters that range from 0-i and X₁ - X_k, which is a total of ik possible arguments.

That leaves us with a runtime of O((ik)²).

The following part is based on my understanding of the OP s question. I m not sure if the distance of every point in X from the i-sized subset is the sum of the distances of every point from every other point in the subset, or the sum of the distances of every point in X from the subset itself.
I.e. sigma of x in X of (sum of distances of x from every point in the subset) OR sigma of x in X of (distance of x from the subset which is the minimum distance from x to any point in the subset)

我假定后者。

我们可以通过选择上述<条码>O(ik)检查来缩短时间。 我们注意到,这些要素实际上是分类的(尽管在目前情况下是相反的),因为当我们补充这些内容时,我们总是从正确的方面来这样做。 假设它们重新分类,它们将一度脱离可持续发展司的例行工作。 如果从头开始,它们可以分类,则只计算费用<条码>O(klogk)。

Once sorted, checking the distance of each point from a point in the set will be k * logi since for each point we do a binary search. This yields a total running time of O(ik * klogi + klogk)
= O(k² * ilogi).

Finally, we can express that as O(k³logk). Not the fastest solution, but a solution.

我肯定会有更多的选择,但这符合我的两点。