ABC327 E
まとめです。
https://atcoder.jp/contests/abc327/tasks/abc327_e
要約すると、
・テストをn回受けます。
・n回のテストの中からいくつかの結果を選び、重みづけを行います。
・重みづけして処理を行ったスコアのうち、最も高いものを出力してください。
問題文から何となく単純そうなdpということが読み取れます。
ただdpの各要素について一々重みづけを行うのはかなり面倒そうです。
dp[i][j]=max(云々)という形式で表すのは難しいので、その形式で表せそうな部分だけにdpを適用します。
分母は以下のように表せます。
初項(0.9)**(k-1),公比0.9の等比数列の和であることから、k項の和は、
∑(i=0,k-1){0.9}**i
= (1-0.9**k)/(1-0.9)
これにより、分母は10(1-(0.9)**k)になります。
同様に、1200/√kについても、dpを用いる必要はありません。
したがって、今回dpで求めるのは分子のみでいけます。
ステップとしては
1.dpでk(1,2,3...n)について最も高いスコアを求める
2.dp[N][k](1,2,3...n)について、重みづけして答えを求める
という感じ。
dp[i][j]=i個目までのテストで結果をj個選んだときのスコアとし、
dpの遷移は
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]*0.9+p[j])
になります。複雑かもしれないですがdp[i-1][j-1]*0.9+p[j]について
i-1個目までのテストでj個の結果を選んだ時のスコアかi-1個目までのテストでj-1個の結果を選んだ時のスコアにP[j]を追加したもののうち、大きい方になるというのは理解できます。ただ、テストの順番に応じて0.9で処理をしたいです。
現在解ける問題数を3つとしたとき、3つ目の問題のパフォも比較したい場合には
3個目までのテストで結果を3個選ぶと,順番通りにP[1,2,3]を選んだとして
0.81*P[1]+0.9*P[2]+1.0*P[3]
になります。
2個目までのテストで結果を2個選んだ時の最高スコアはP[1,2]を選んだとして
0.9*P[1]+1.0*P[2]
です。
したがって、i-1個目までの結果の中からj-1個選んだ時の最高スコアに0.9をかけることで良い感じになるので、それで比較します。
最後に、dp[-1][各々]について処理を行い結果を出力します。
dpの初期化は-1e9を使ったりすると0.9**5000にだまされるので-infを使っておくと0.9**5000とかに騙されないで済みます
まとめ
自分で書いてて、解説が分かりづらいなと思ったので後でまとめ直す
