La méthode de Monte Carlo était inutile, alors je l'ai fait sérieusement. Si la valeur attendue est n, alors n = p * (1 + n) + (1 --p) * 0, donc n = p / (1 --p) Sera.
p = float(input())
print(p / (1 - p))
Si vous recherchez "Pro de la concurrence d'augmentation monotone au sens large", le code de POJ-3666: Création de la note apparaîtra, vous pouvez donc commenter et publier le code sur le côté de la colonne de diminution monotone au sens large (cruel).
Addendum: résolu correctement. Lorsque Y i-1 </ sub> après le mouvement est x, si la distance totale déplacée jusqu'à ce point est dp [i -1] [x], alors dp [i ] [x] est 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]))
En Python, il devient TLE et ne peut être transmis que dans PyPy. À propos, bien qu'il soit écrit en 2 dimensions, il fonctionne en réalité en 1 dimension car il n'y a pas de chevauchement. De plus, la destination de Y i </ sub> Il n'y a pas de problème avec les coordonnées de Y 1 </ sub>, ..., Y N </ sub>. Si vous écrivez avec ce qui précède à l'esprit, le code passera même en Python. ..
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