SRM656 Div1 Easy RandomPancakeStack
問題
パンケーキが $N$ 枚あり、$i$ 番目のパンケーキは直径が $i$ でおいしさが $d[i]$ である。 あなたは以下の操作にしたがってパンケーキを積み上げる(スタックを作る)。
- もしパンケーキがなければ操作をやめる
- まだ選ばれていないパンケーキから一様ランダムに 1 枚選ぶ
- スタックの一番上のパンケーキより大きい場合は操作をやめる
- そうでなければスタックの一番上に載せ 1. に戻る
このような操作の後、スタックに積まれたパンケーキのおいしさの総和の期待値を求めなさい。
方針
$ dp(i,j) = $ 「$i$ より大きいケーキだけを使える。また、今現在 $j$ 枚使っている。残りのパンケーキでの期待値」 とおき、メモ化再帰。
実装
double dp[1<<8][1<<8];
class RandomPancakeStack {
public:
int N;
vi d;
double expectedDeliciousness( vector <int> d_ ) {
d = d_;
N = d.size();
reverse(all(d));
rep(i,1<<8)rep(j,1<<8) dp[i][j] = -1;
return f(0,0);
}
double f(int lb, int used){
double & res = dp[lb][used];
if(res != -1) return res;
res = 0;
loop(i,lb,N) res += (d[i]+f(i+1,used+1)) / (N-used);
return res;
}
};