算法动态程序

Question

我今天正在阅读一本来自爱尔兰的计算机科学杂志，它有一个回答这个问题的竞赛。谁能帮我解决一下。

问题。

给定 x1….., xn，确定 EMP 应该被激活的次数消灭最大数量的外星人。

例子。假设 n = 4 和 x1…x4 = 1, 10, 10, 1。那么最好的解决方案是是在第3、4分钟激活EMP。第3分钟，它摧毁了min(10,3^2) = 9 个外星人。然后在第 4 分钟，它摧毁了 min(1,1^2) = 1 个外星人。这总共给出了 10 个外星人。

2 个问题

(a) 令 S(j) 表示为子问题消灭的外星人的最大总数由仅在前 j 分钟到达的外星人组成。给出一个递归公式对于 S(j)。另外，写下基本情况。 (提示:对于 S(j)，您总是激活EMP 在第 j 分钟。假设之前的激活发生在第 i 分钟。尝试 i 的所有可能性并取最大值。)

(b) 给出这个问题的动态规划算法。分析时间和算法的空间复杂度。

要点:-一群外星人在 n 分钟内到达。在第 i 分钟，xi 外星人到达。根据遥感数据，你可以提前知道这个序列x1…xn。

你可以使用电磁脉冲 (EMP)，它可以摧毁一些的外星人。 EMP 的功率取决于允许充电多长时间向上。为了精确起见，如果自从上次使用 EMP 后已经过了 j 分钟，它能够摧毁j2外星人。

EMP 只会摧毁在它被激活的那一刻到达的外星人。在换句话说，它不会摧毁任何早晚到达的外星人。

因此，如果它在第 k 分钟被使用，并且自上次使用以来已经过去了 j 分钟，那么它会摧毁 min(xk, j2) 个外星人(即 xk 或 j2 中较小的那个)。

每次使用后 EMP 将完全耗尽。我们还假设 EMP 开始关闭(在第 0 分钟)完全耗尽。

Answer 1

(a) 这个提示真的暴露了它。 S(0) = 0显然，和S(1) = 1 .我们有:

S(j) = max{S(i) + min(x[j], (j - i)^2) : 0 <= i < j} .这真的只是按照提示所说的去做。以下是它在您的示例中的运行方式:

1 10 10 1
S(0) = 0
S(1) = 1
S(2) = max{S(0) + min(x[2], (2-0)^2), S(1) + min(x[2], (2 - 1)^2)} =
     = max{0 + 4, 1 + 1} 
     = 4
S(3) = max{S(0) + min(x[3], (3 - 0)^2), S(1) + min(x[3], (3-1)^2), S(2) + min(x[3], (3-2)^2)}
     = max{0 + 9, 1 + 4, 4 + 1}
     = 9
S(4) = max{S(0) + min(x[4], (4 - 0)^2), ..., S[3] + min(x[4], (4-3)^2)}
     = max{0 + 1, ..., 9 + 1}
     = 10

(b) 我上面已经解决了。按住S作为一个数组。由于每个 S(i) 的计算需要迭代所有 j < i , 每个 S(i)需要 O(n)时间，所以整个算法是O(n^2) .