动态规划-任务调度

这是一个在我的大学课堂上没有人能正确回答的"闪测"问题:

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个槽，解是有效的

我对这个问题的第一次尝试，可能有更快的方法。设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

相关内容