算法动态程序 [英] Algorithm dynamic program

问题描述

我在读今天的计算机科学杂志上，来自爱尔兰，它有回答这个问题的一个竞争。任何人都可以帮我解决这个问题。

I was reading a computer science magazine today from Ireland and it has a competition for answering this question. could anyone help me to solve it.

这个问题。

由于X1 ... ..，XN，决定倍EMP应该被激活 摧毁外星人的最大数量。

Given x1….., xn, determine the times that the EMP should be activated to destroy the maximum number of aliens.

为例。假设n = 4时和X1〜X4 = 1，10，10，1。然后最好的解决办法 要激活EMP在第3和第4分钟。在第3分钟，它破坏 分钟（10,3 ^ 2）= 9外星人。然后在第4分钟，它破坏分钟（1,1 ^ 2）= 1外星人。本 给出总共10外星人。

Example. Suppose n = 4 and x1…x4 = 1, 10, 10, 1. Then the best solution would be to activate the EMP in the 3rd and 4th minutes. In the 3rd minute, it destroys min(10,3^2) = 9 aliens. Then in the 4th minute, it destroys min(1,1^2) = 1 alien. This gives a total of 10 aliens.

2的问题

（一）令S（J）表示外星人摧毁的子问题的最大总数 由到达仅在第j个分钟的外国人。举一个递推公式 对于S（J）此外，记下基本情况。 （提示：为S（j）中，你总是激活 EMP在第j分钟。假设previous活化发生在第i个分钟。 请尝试我所有的可能性，并采取最大。）

(a) Let S(j) denote the maximum total number of aliens destroyed for the subproblem consisting of the aliens arriving in the first j minutes only. Give a recursive formula for S(j). Also, write down the base case. (Hint: for S(j), you always activate the EMP at the j-th minute. Suppose the previous activation happens at the i-th minute. Try all possibilities of i and take the maximum.)

（B）给出了动态规划算法针对此问题。分析的时间和 空间的算法的复杂度。

(b) Give a dynamic programming algorithm for this problem. Analyze the time and space complexity of the algorithm.

要点： - 外星人的群到达过n分钟的过程。在第i分钟，喜外星人 到达。基于遥感数据，你就知道这个序列X1 ... xn的提前。

Key points:- A swarm of aliens arrive over the course of n minutes. In the i-th minute, xi aliens arrive. Based on remote sensing data, you know this sequence x1… xn in advance.

您在您的处置的电磁脉冲（EMP），它可以破坏一些 的外星人。环境管理计划的动力取决于长，它被允许收取 向上。为了使这个precise，如果将j分钟之后的EMP是最后一次使用时， 能够摧毁J2外国人。

You have at your disposal an electromagnetic pulse (EMP), which can destroy some of the aliens. The EMP's power depends on how long it has been allowed to charge up. To make this precise, if j minutes have passed since the EMP was last used, it is capable of destroying j2 aliens.

在EMP只有破坏到达它已被激活的确切分钟的外星人。在 换句话说，它不会破坏任何外星人提前或推迟到达。

The EMP only destroys aliens arriving in the exact minute that it is activated. In other words, it does not destroy any aliens arriving earlier or later.

因此​​，如果它被用在第k个分钟，并已经Ĵ分钟，因为它是previously使用，那么它会破坏分钟（XK，J2）外国人（即，取其XK或J2是较小）。

Therefore, if it is used in the k-th minute, and it has been j minutes since it was previously used, then it destroys min(xk, j2) aliens (i.e., whichever xk or j2 is smaller).

在每次使用EMP将被完全耗尽。我们还假设EMP开始 关闭（在第0分钟），为完全耗尽。

After each use the EMP will be completely drained. We also assume the EMP starts off(at the 0-th minute) as completely drained.

推荐答案

（一）的提示给它拿走真的。 S（0）= 0 显然，和 S（1）= 1 。我们有：

(a) The hint gives it away really. S(0) = 0 obviously, and S(1) = 1. We have that:

S（j）条=最大值{S（I）+分（X [J]，（J - I）^ 2）：0℃= I＆LT; Ĵ} 。这真的只是做什么提示说。下面是它可以运行在您的例子：

S(j) = max{S(i) + min(x[j], (j - i)^2) : 0 <= i < j}. This really just does what the hint says. Here's how it will run on your example:

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

（二）我上面已经解决了它。只需按住取值作为数组。由于每个计算 S（I）要求所有 J＆LT的迭代;我，每个 S（I）需要 O（N）的时间，所以整个算法是为O（n ^ 2）。

(b) I already solved it above. Just hold S as an array. Since the computation of each S(i) requires iteration of all j < i, each S(i) takes O(n) time, so the entire algorithm is O(n^2).

这篇关于算法动态程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！