1

这是一个在我大学课堂上的“快速测试”中没有人能够正确回答的问题：

我们得到：

int N < 1000 个时间槽

int[] C: -10 000 <= C[i] <= 10 000 对应每个槽的支付

int T：我们必须使用的插槽数

问题表述如下：

一个懒惰的工人在整个工作日中有 N 个时间段。

对于每个时间段，他都会获得一定的报酬（C[i] - 不切实际地，它也可能是负数）。

他想选择正好 T 个时隙的区间，这样他就能得到最大的报酬。我们必须选择他将工作的间隔。例如 [1, 4] - 从第一个插槽到第四个。

问题是，他每次休息，回来上班，他工作的第一个时段是不会发工资的，因为他又开始习惯工作了，就像一个懒人一样。因此，我们也可以选择像 [5, 5] 这样的空区间，如果我们有负支付，这可能会派上用场。无论事先与插槽关联什么付款，这些都将获得付款 0。

为了更清楚，我将举一个简单的例子：

假设我们有 N=5 个时隙，我们想选择 T=4。C={3, 9, 1, 1, 7}

最好的解决方案是区间 [1, 2]；[4, 5] 总共支付 9+7=16

我们一共覆盖了 T=4 个时隙，解是有效的。

4

1 回答 1

0

我第一次尝试解决这个问题，但可能会有更快的速度。令 f(i, j, t) 表示在子数组 N[i, j]（包括 i 和 j）内拟合 t 个点的最佳方法，这样 N[i] 被覆盖，N[j] 被覆盖。现在注意 f(i, j, t) = max { f(i, j-1, t-1) + C[j], max_{1 < k < j - i} f(i, jk, t- 1）}。基本情况是 f(i, j, t) = 0 if (j - i + 1 < t), f(i, i, 1) = 0, f(i, j, 1) = inf 和 f( i, j, 2) = C[i] + C[j]。我认为复杂度是 O(N^3 * T)，因为表 f 的大小为 N^2 * T，在 f 内部，我们需要取 (k < j - i) 的最大值来获得 N 的附加因子在我们的复杂性中。因此 O(N^3 * T)。希望我没有忽略问题中的某些内容。

为了从表 f 中找到解决方案，只需执行 max_{i,j} f(i, j, T)。

于 2013-03-16T10:56:55.807 回答