topcoder: YetAnotherRobotSimulation

又一次暴力求解被羞辱，这个题感觉一定可以for循环代替递归，然而经验值不足（智商感人的委婉说法😢）没能在放弃之前想出来，于是再次拿来主义：

class YetAnotherRobotSimulation:
    def getMaximumProbability(self,L,x,y):
        px = tuple(x)
        py = tuple(y)
        tl = len(px)
        '''
        tp = []
        for i in range(0, tl):
            tp.append((px[i],py[i]))
        '''

        tp = {}
        for i in range(0, tl):
            tp[(px[i],py[i])] = True

        c = []
        # 一张屌炸天的排列组合速查表；生成它需要一点数学推导：
        # C(4,2) = C(3,1) + C(3,2)
        # 这里隐含了DP思想，知道了C(3,1)和C(3,2)这两种组合数，
        # 那么现在新加入一个元素，在4个元素里面挑出2个，无非是：
        # 要么用新的元素和原来所有1个元素的组合组成新的2元组，
        # 要么不选这个新的，直接用原来3个里面已有的2元组
        for i in range(0, 51):
            c.append([])
            for j in range(0, i+1):
                if j == 0:
                    c[i].append(1)
                else:
                    if j > i-1:
                        c[i].append(c[i-1][j-1])
                    else:
                        c[i].append(c[i-1][j-1]+c[i-1][j])

        m = 0
        u = r = l = d = 0
        # 只要按顺序列举出所有的指令seq组合即可，
        # 指令之间的排序根本不影响最终结果
        for u in range(0, L+1):
            for r in range(0, L-u+1):
                for l in range(0, L-u-r+1):
                    d = L-u-r-l
                    s = 0
                    pu = pr = pl = pd = 0
                    # 由于指令顺序不重要，
                    # 那么只要枚举出每种指令可能生效的次数即可
                    for pu in range(0,u+1):
                        for pr in range(0,r+1):
                            for pl in range(0,l+1):
                                for pd in range(0,d+1):
                                    # 这是一个小优化，事先准备好目标集合字典：m
                                    # 比在运行中不断用in来判断要快很多（1/4）
                                    #if (pr-pl, pu-pd) in tp:
                                    if tp.get((pr-pl, pu-pd), False):
                                        # 虽然生效指令的个数决定了最终到达的位置
                                        # 但是我们还是需要知道有多少种组合方式
                                        # 因为要算概率，需要知道当前指令序列能有
                                        # 多少种方式到达这里，所有能够到达目标
                                        # 集合的方式除以某个指令序列可能的所有
                                        # 生效形式（1<<L）就是它的到达目标概率
                                        s += c[u][pu]*c[r][pr]*c[l][pl]*c[d][pd]
                                        m = max(s, m)

        return float(m)/(1<<L)

class YetAnotherRobotSimulation:

def getMaximumProbability(self,L,x,y):

px = tuple(x)

py = tuple(y)

tl = len(px)

'''

tp = []

for i in range(0, tl):

tp.append((px[i],py[i]))

'''

tp = {}

for i in range(0, tl):

tp[(px[i],py[i])] = True

c = []

# 一张屌炸天的排列组合速查表；生成它需要一点数学推导：

# C(4,2) = C(3,1) + C(3,2)

# 这里隐含了DP思想，知道了C(3,1)和C(3,2)这两种组合数，

# 那么现在新加入一个元素，在4个元素里面挑出2个，无非是：

# 要么用新的元素和原来所有1个元素的组合组成新的2元组，

# 要么不选这个新的，直接用原来3个里面已有的2元组

for i in range(0, 51):

c.append([])

for j in range(0, i+1):

if j == 0:

c[i].append(1)

else:

if j > i-1:

c[i].append(c[i-1][j-1])

else:

c[i].append(c[i-1][j-1]+c[i-1][j])

m = 0

u = r = l = d = 0

# 只要按顺序列举出所有的指令seq组合即可，

# 指令之间的排序根本不影响最终结果

for u in range(0, L+1):

for r in range(0, L-u+1):

for l in range(0, L-u-r+1):

d = L-u-r-l

s = 0

pu = pr = pl = pd = 0

# 由于指令顺序不重要，

# 那么只要枚举出每种指令可能生效的次数即可

for pu in range(0,u+1):

for pr in range(0,r+1):

for pl in range(0,l+1):

for pd in range(0,d+1):

# 这是一个小优化，事先准备好目标集合字典：m

# 比在运行中不断用in来判断要快很多（1/4）

#if (pr-pl, pu-pd) in tp:

if tp.get((pr-pl, pu-pd), False):

# 虽然生效指令的个数决定了最终到达的位置

# 但是我们还是需要知道有多少种组合方式

# 因为要算概率，需要知道当前指令序列能有

# 多少种方式到达这里，所有能够到达目标

# 集合的方式除以某个指令序列可能的所有

# 生效形式（1<<L）就是它的到达目标概率

s += c[u][pu]*c[r][pr]*c[l][pl]*c[d][pd]

m = max(s, m)

return float(m)/(1<<L)

topcoder: YetAnotherRobotSimulation

Related

Leave a Reply Cancel reply

Share this:

Related

Leave a Reply Cancel reply