SRM656 Div1 Easy RandomPancakeStack

2015/04/18 (Sat) SRM DP

問題

問題文

パンケーキが $N$ 枚あり、$i$ 番目のパンケーキは直径が $i$ でおいしさが $d[i]$ である。 あなたは以下の操作にしたがってパンケーキを積み上げる(スタックを作る)。

  1. もしパンケーキがなければ操作をやめる
  2. まだ選ばれていないパンケーキから一様ランダムに 1 枚選ぶ
  3. スタックの一番上のパンケーキより大きい場合は操作をやめる
  4. そうでなければスタックの一番上に載せ 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;
    }
};