CodeThanksFestival2014A日程 G.通勤電車と気分

その他

問題

N人とK席があり、各人は順番に以下のルールによって席に座る。
・i番目の人はp[i]の確率で「空いていれば座る」、(1-p[i])の確率で「両隣に人がいなければ座る」
・どちらも満たせない場合は、座らない
空いている席数の期待値を求める。

考え方

空いている席の位置は区別する必要がないので、
dp[i+1][j][k]=人iまで処理して、j人座って、k番目まで席が埋まっているときの確率
で求められる。
dp[i][j][k]の時、j==kなら空いていないので、k+1番目以降を使い、j