1

这个问题很容易在 O(n 3 ) 时间内天真地解决。问题是这样的：

数轴上有 N 个独特的点。您想用一组间隔覆盖数轴上的每个点。您可以将间隔放置在任何地方，B + MX创建间隔的成本，其中B是创建间隔的初始成本，是间隔 长度的一半X，并且是每个间隔长度的成本。您想找到覆盖每个间隔的最低成本。M

样本数据：

Points = {0, 7, 100}
B = 20
M = 5

因此最佳解决方案是 57.50，因为您可以以 20 + 3.5×5 的成本构建一个区间 [0,7]，并以 100 + 0×5 的成本在 [100,100] 构建一个区间，总和为 57.50。

我有一个 O(n 3 ) 解决方案，其中 DP 是从[left, right]. 所以答案将在DP[1][N]. 对于每一对(i,j)我只是迭代k = {i...j-1}和计算DP[i][k] + DP[k + 1][j]。

然而，这个解决方案是 O(n 3 ) （我认为有点像矩阵乘法）所以它在 N > 2000 时太慢了。有什么办法可以优化这个吗？

4

1 回答 1

2

这是一个二次解：

  1. 按坐标对所有点进行排序。叫点p。

  2. 我们将保留一个数组A，A[k]以便覆盖第一k点的最低成本。设置A[0]为零，所有其他元素设置为无穷大。

  3. 对于每个kfrom 0ton-1和每个lfrom k+1to n，设置A[l] = min(A[l], A[k] + B + M*(p[l-1] - p[k])/2);

最后，您应该能够说服自己，这是涵盖所有要点A[n]的最低成本。n（我们考虑了所有可能的最小覆盖间隔，并且在某种意义上我们是从“左到右”这样做的。）

您可以加快速度，使其在 O(n log n) 时间内运行；将步骤 3 替换为以下内容：

设置A[1] = B。对于每个kfrom2到n，设置A[k] = A[k-1] + min(M/2 * (p[k-1] - p[k-2]), B)。

这里的想法是我们要么扩展前一个区间以覆盖下一个点，要么我们在 结束前一个区间p[k-2]并在 开始一个新区间p[k-1]。做出这个决定我们唯一需要知道的是两点之间的距离。

另请注意，在计算 时A[k]，我只需要 的值A[k-1]。特别是，您不需要存储整个数组A；只有它最近的元素。

于 2012-12-15T06:05:38.410 回答