ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Educational DP Contest / DP まとめコンテスト I - Coins

問題
提出コード

解法

確率です。
dp[i][j] = i番目までのコインを投げて、表がj回出る確率、とします。
もちろん、dp[0][0] =1です。
答えは、dp[N][j] (ただし、j \geqq (N+1)/2 )の総和になります。
i-1番目までのコインを投げてj回表が出ていた場合、i番目のコインを投げると表の回数がjになるか、j+1になります。前者は1-p_{i}の確率を引いて裏が出た場合、後者はp_{i}の確率を引いて表が出た場合です。
これをもとにして遷移を考えると、
dp[i][j] = dp[i-1][j]\times (1-p_{i}) + dp[i-1][j-1]\times p_{i}
となります。あとは遷移をもとにDPを行い、合計値を求めれば答えになります。