問題
サイズNの配列が与えられる。i番目の要素はパンケーキの美味しさを示し、サイズはi+1とする。
以下の操作を行ったあとの美味しさの総和の期待値を求めよ。
- 選択されていないパンケーキを一様ランダムに選ぶ
- 選んだパンケーキのサイズがスタックの上にあるパンケーキより大きい場合は、パンケーキをスタックに積まずに終了する
- 選んだパンケーキをスタックに積み、処理を終了する
解法
dp[T][S]とし、動的計画法を用いる。Tはスタックに積むことができるパンケーキの数、Sはスタックのサイズを示す。
dp[T][S] =
という式が成り立つので計算をする。
計算量