Die Monte-Carlo-Methode war nutzlos, also habe ich es ernsthaft getan. Wenn der erwartete Wert n ist, dann ist n = p * (1 + n) + (1 - p) * 0, also n = p / (1 - p) Wird sein.
p = float(input())
print(p / (1 - p))
Wenn Sie nach "Broad-Sense Monotonous Enhance Competition Pro" suchen, wird der Code für POJ-3666: Making the Grade angezeigt, sodass Sie den Code auskommentieren und auf der Seite der Broad-Sense Monotonous Reduction-Spalte (grausam) veröffentlichen können.
Nachtrag: Richtig gelöst. Wenn Y i-1 </ sub> nach der Bewegung x ist und die Gesamtdistanz bis zu diesem Punkt dp [i -1] [x] beträgt, dann dp [i ] [x] ist min (dp [i - 1] [0], dp [i - 1] [1], ..., dp [i - 1] [x]) + abs (Y i <) / sub> --x).
N = int(input())
Y = list(map(int, input().split()))
dp = [[0] * (10 ** 4 + 1) for _ in range(N)]
for i in range(N):
t = float('inf')
for j in range(10 ** 4 + 1):
t = min(t, dp[i - 1][j])
dp[i][j] = t + abs(Y[i] - j)
print(min(dp[N - 1]))
In Python wird es zu TLE und kann nur in PyPy übergeben werden. Obwohl es in zwei Dimensionen geschrieben ist, funktioniert es tatsächlich in einer Dimension, da es keine Überlappung gibt. Auch das Ziel von Y i </ sub> Es gibt kein Problem mit den Koordinaten von Y 1 </ sub>, ..., Y N </ sub>. Wenn Sie unter Berücksichtigung der oben genannten Punkte schreiben, wird der Code auch in Python übergeben. ..
N = int(input())
Y = list(map(int, input().split()))
a = sorted(set(Y))
dp = [0] * len(a)
for i in range(N):
t = float('inf')
for j in range(len(a)):
t = min(t, dp[j])
dp[j] = t + abs(Y[i] - a[j])
print(min(dp))
Recommended Posts