1

根据this thread，我尝试用python编写算法。

这是我的代码：

def shoot(aliens):

    s=[0]*1000
    s[0]=0
    s[1]=1
    num=len(aliens)
    for j in xrange(2,num):
        a=[0]*1000
        for i in xrange(0,j):
            a[i]=s[i]+min(int(aliens[j]),f[j-i]) ## possible tries
        s[j]=max(a)                      ##f[i] is the i-th finonacci number 

    return s[len(aliens)-1]

它通过显示被摧毁的最大外星人来工作。但是，我想打印出他们射杀外星人的时间。我的想法是从最后一次击杀开始，即 len(aliens)-1 并找出在“(len(aliens)-1)”-th 射击之前最后一次射击是什么。然后继续做同样的事情，直到我们到达第一次拍摄。

为此，我存储了所有可能的尝试并将最后一次拍摄与它们进行比较以找到倒数第二次拍摄，但运行时间会很长，并且显示错误的结果。我不确定它是否正确，但我试图实现它但我失败了。

有人对此有想法吗？谢谢你！

PS：看不懂我写的请追问。另外，我不想从上面的线程中复制问题，因为它很长。如果打扰到你，我很抱歉。

4

1 回答 1

2

I don't know where you got the fibonacci numbers from (the original recursive relation had (j - i)^2)

Regardless, the easiest way would be to keep track of a parent array while doing the dp. For example:

def getTimes(aliens):
    n = len(aliens)
    dp = [0] * n #your s array. I'm just used to using dp for dp tables
    parent = [-1] * n
    dp[1] = 1
    for i in range(2, n):
        max = 0; #assuming there can't be a negative number of aliens. 
        for j in range(0, i):
            x = dp[j] + min(int(aliens[i]), (i - j) * (i - j))
            if(x >= max):
                max = x
                parent[i] = j
        dp[i] = max;
    times = getTimesRec(n - 1, [], parent)
    return times

def getTimesRec(i, times, parent):
    if(i == -1):
        return times
    getTimesRec(parent[i], times, parent)
    times.append(i)
    return times

I haven't tested this, but the idea behind it should be fine. Essentially whenever you figure out when the last alien was shot you keep track of it in the parent array. You can then go from the end and store the times into a list in reverse order recursively (as shown) or using a stack.

You could also probably make this run in O(nlogn) by using a binary search similar to longest increasing subsequence. I'm too lazy to think about how to do it.

Edit: Hopefully I can clear up some of the confusion. All the parent array does is store when the previous shot occurred given a time frame.

So for example let's say that you shoot at time 4, 19, and 23. This means that the parent array looks like this:

parent[23] = 19
parent[19] = 4
parent[4] = -1

So given this array we can figure out the reverse order of times by just adding 23 to a list then parent[23] then parent[parent[23]] and so on until we reach -1. The recursion is just there to reverse this chain all in one step.

于 2013-07-20T00:33:13.907 回答