Cより簡単…?
http://codeforces.com/contest/518/problem/D
問題
N人の人が並んでいる。
時間1ごとに先頭の人が確率pでエスカレータに乗る。
時間T後、エスカレータに乗った人数の期待値を答えよ。
解法
時間ごとにエスカレータに乗った人数に対応する確率を更新していく典型DP。
最後に人数を確率で重みづけ平均を取ればよい。
int N,T; double P; double dp[2020][2020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>P>>T; dp[0][0]=1; FOR(i,T) { FOR(x,N) { dp[i+1][x+1]+=dp[i][x]*P; dp[i+1][x]+=dp[i][x]*(1-P); } dp[i+1][N]+=dp[i][N]; } double ret=0; FOR(i,N+1) ret += dp[T][i]*i; _P("%.12lf\n",ret); }
まとめ
かなり典型だと思うけど、なんでこれDに置いたんだろう。