[Python] DP ABC184D

Soit dp (X, Y, Z) la réponse lorsqu'il y a X pièces d'or, Y pièces d'argent et Z pièces de cuivre. Lorsque l'un des X, Y, Z vaut 100, dp (X, Y, Z) = 0. Sinon, en considérant les trois caisses dont la pièce a été tirée,

dp(X,Y,Z)=\frac{X}{X+Y+Z}(dp(X+1,Y,Z)+1)+\frac{Y}{X+Y+Z}(dp(X,Y+1,Z)+1)+\frac{Z}{X+Y+Z}(dp(X,Y,Z+1)+1)

Ce sera. (Probabilité de tirer des pièces d'or x nombre d'opérations prévu lors du tirage de pièces d'or + pièces d'argent ...)

Vous pouvez trouver la réponse en effectuant DP selon cette formule. La mise en œuvre est facile avec un mémorandum récursif.

`Exemple de code`


import sys
sys.setrecursionlimit(10 ** 6)  #Augmenter la limite supérieure du nombre de récurrences


def dfs(x, y, z):  #Récurrence mémorisée
    if dp[x][y][z] >= 0: #Si la valeur est déjà connue, renvoyez-la telle quelle.
        ret = dp[x][y][z]
    else:  #Si la valeur n'est pas connue, recherchez la valeur par une formule progressive.
        ret = 0
        S = x + y + z
        ret += x / S * (dfs(x+1, y, z) + 1)
        ret += y / S * (dfs(x, y+1, z) + 1)
        ret += z / S * (dfs(x, y, z+1) + 1)
        dp[x][y][z] = ret  #Note
    return ret


X, Y, Z = map(int, input().split())
M = 100
dp = [[[-1] * (M + 1) for _ in range(M + 1)] for _ in range(M + 1)]
#Condition de terminaison (initialisation)
for i in range(A, M + 1):
    for j in range(B, M + 1):
        for k in range(C, M + 1):
            if i == M or j == M or k == M:
                dp[i][j][k] = 0

# dp(X, Y, Z)La réponse que
print(dfs(X, Y, Z))