algorithm - 动态规划最优广播

Question

我知道如何以通常的方式解决这个问题，而不是使用动态规划。如果您能友好地向我解释解决方案/给我一个大概的想法/伪代码。非常感谢。

输入由序列 R = hR0, . . . ,Rni 的非负整数，和一个整数 k。数字 Ri 表示在时间 i 请求某些特定信息的用户数(比如来自 www 服务器)。

如果服务器在某个时间 t 广播此信息，则请求该信息的所有用户的请求严格在时间 t 之前得到满足。服务器最多可以广播此信息 k 次。目标是选择 k 次广播，以最小化请求/用户必须等待的总时间(在所有请求中)满足他们的要求。

例如，假设输入为 R = 3、4、0、5、2、7(因此 n = 6)和 k = 3。那么一种可能的解决方案(没有人声称这是最佳解决方案)将在第 2、4 和 7 次广播(请注意，这是显而易见的在每个最优调度中，如果 Rn 6= 0，则在时间 n + 1 有一个广播)。时间 1 的 3 个请求将然后必须等待1个时间单位。时间 2 的 4 个请求将不得不等待 2 个时间单位。的 5 个请求然后时间 4 必须等待 3 个时间单位。时间 5 的 2 个请求将不得不等待 2 个时间单位。这时间 6 的 7 个请求将不得不等待 1 个时间单位。因此，该解决方案的总等待时间为3 × 1 + 4 × 2 + 5 × 3 + 2 × 2 + 7 × 1..

I/O 描述。输入:n 和 k，在第一行以一个空格分隔，然后在第二行以 R 分隔。输出:k次的序列。

Answer 1

1. 设置第i个广播时间。
2. 求解 R' = {Rj | j>=i} 和 k' = k-1

当然，您将需要存储所有子解决方案以使其成为动态规划算法而不是简单的递归。

请注意，您必须从 k-1 次广播开始，因为第 k 次广播总是在最后一次非零用户之后。

问题出在第 1 步。您可以尝试所有可能的位置(我认为最坏情况下的时间复杂度为 n*k)。我建议你先试试这个朴素的方法，在一些数据上测试一下，看看你能不能想出更好的方法来找到第一个广播的位置。