[Python] DP ABC184D

Sei dp (X, Y, Z) die Antwort, wenn es X Goldmünzen, Y Silbermünzen und Z Kupfermünzen gibt. Wenn eines von X, Y, Z 100 ist, ist dp (X, Y, Z) = 0. Wenn nicht, unter Berücksichtigung der drei Fälle, in denen eine Münze gezogen wurde,

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)

Es wird sein. (Wahrscheinlichkeit des Ziehens von Goldmünzen x erwartete Anzahl von Operationen beim Ziehen von Goldmünzen + Silbermünzen ...)

Sie finden die Antwort, indem Sie DP gemäß dieser Formel ausführen. Es ist einfach durch Wiederholung von Memorandums zu implementieren.

`Beispielcode`


import sys
sys.setrecursionlimit(10 ** 6)  #Erhöhen Sie die Obergrenze für die Anzahl der Wiederholungen


def dfs(x, y, z):  #Gespeicherte Wiederholung
    if dp[x][y][z] >= 0: #Wenn der Wert bereits bekannt ist, geben Sie ihn unverändert zurück.
        ret = dp[x][y][z]
    else:  #Wenn der Wert nicht bekannt ist, suchen Sie ihn nach einer schrittweisen Formel.
        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  #Memo
    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)]
#Kündigungsbedingung (Initialisierung)
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)Die Antwort darauf
print(dfs(X, Y, Z))