きままにものづくり

日々の気付いたことなんかを書いてます。

SRM656Div1Easy

問題

サイズNの配列が与えられる。i番目の要素はパンケーキの美味しさを示し、サイズはi+1とする。
以下の操作を行ったあとの美味しさの総和の期待値を求めよ。

  • 選択されていないパンケーキを一様ランダムに選ぶ
  • 選んだパンケーキのサイズがスタックの上にあるパンケーキより大きい場合は、パンケーキをスタックに積まずに終了する
  • 選んだパンケーキをスタックに積み、処理を終了する

解法

dp[T][S]とし、動的計画法を用いる。Tはスタックに積むことができるパンケーキの数、Sはスタックのサイズを示す。
dp[T][S] =  \displaystyle{ \frac{1}{N-S}\sum^{T}_{i=0}(d[i] + dp[i][s+1] ) }
という式が成り立つので計算をする。

計算量

 O(N^3)

コード