ABC327E - Maximize Rating

解法1：dp

考え方

Editorial - HHKB Programming Contest 2023(AtCoder Beginner Contest 327)

アライグマ「E問題はDPなのだ！　分子のところだけ見ると、コンテストに参加するたびに、新分子＝パフォ＋旧分子×0.9になるのだ。残りはkだけで決まるから、
dp[i][k]=i番目まででk回参加したときの分子の最大値
でDPして最後にk=1,2,…でそれぞれレートがいくつになるか調べればいいのだ！」

— 競技プログラミングをするフレンズ (@kyopro_friends) November 4, 2023

回答例

N = int(input())
P = list(map(int, input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N):
    for j in range(N):
        if j > i:continue
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], 0.9*dp[i][j] + P[i])

ans = -1<<60
denom = 1
for k in range(1, N+1):
    ans = max(ans, dp[N][k]/denom - 1200/(k**0.5))
    denom = 0.9 * denom + 1

print(ans)