2015年3月1日日曜日

CF 518D. Ilya and Escalator

問題

エスカレーターの前にn人並んでいる。先頭の人は1分毎に確率pで勇気を振り絞ってエレベーターに乗り、1-pでその場にとどまる。エレベーターに乗れるのは先頭の人だけ。また、一度乗ったエレベーターは二度とおりることはない(こわい)
この時、t分後にエレベーターに乗っている人数の期待値を求める問題。

解法

前からi番目の人がt分以内に乗る確率をDPで求めて足す。

0 件のコメント:

コメントを投稿