算法动态规划
我今天读了一本来自爱尔兰的计算机科学杂志，它有一个回答这个问题的竞赛。有人能帮我解决这个问题吗？
问题所在。
给定x1…..，xn，确定EMP应该被激活以摧毁最大数量的外星人的次数。
举例说明。假设n=4且x1…x4 = 1，10，10，1。那么最好的解决方案是在第3分钟和第4分钟激活电磁脉冲。在第三分钟，它销毁了min(10,3^2) =9个外星人。然后在第四分钟，它销毁min(1,1^2) =1个外星人。这总共给出了10个外星人。
2个问题
(a)设S(j)表示仅在前j分钟内到达的外星人所组成的子问题的最大外星人总数。给出了S(j)的一个递推公式。另外，写下基本情况。(提示:对于S(j)，您总是在第j分钟激活EMP。假设前一次激活发生在第i分钟。尝试i的所有可能性，并采用最大值。)
(b)给出了该问题的动态规划算法。分析了该算法的时间复杂度和空间复杂度。
要点：-一群外星人在n分钟内到达。在第i分钟，习的外星人到达。基于遥感数据，你知道这个序列x1…提前xn。
你可以使用电磁脉冲(EMP)，它可以摧毁一些外星人。电磁脉冲的功率取决于它被允许充电的时间。准确地说，如果自上次使用电磁脉冲以来已经过了j分钟，它就能够摧毁j2外星人。
电磁脉冲只会在它被激活的那一分钟摧毁到达的外星人。换句话说，它不会摧毁任何早到或晚到的外星人。
因此，如果它是在第k分钟使用的，并且从它之前使用到现在已经有j分钟了，那么它将销毁min( xk，j2)个外星人(即，以xk或j2中较小的那个为准)。
每次使用后，EMP都会被完全排干。我们还假设EMP开始(在第0分钟)完全耗尽。
回答 1
Stack Overflow用户
发布于 2012-03-29 01:35:58
(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)。
https://stackoverflow.com/questions/9911823
复制相似问题
腾讯云开发者
