AtCoder Regular Contest B - せんべい

問題概要

リンク

• 1 ~ Nまでの数字が書かれたせんべいがランダムな順番で与えられる
• シカは1枚目から順にせんべいを食べるか、食べないか選ぶ
• シカは全部でK枚のせんべいを食べられる
• シカはn枚目のせんべいを見ている時, 1 ~ n枚目のせんべいの大小関係がわかる
• シカはNの数字が書かれたせんべいを食べられるよう最適な選択を取る
• シカがNの数字が書かれたせんべいを食べられる確率を求める

解法

動的計画法。
dp[n][k]:=n番目のせんべいを見ている時、まだNを食べていないとする。あとk枚食べられる時、Nを食べられる確率。
メモ化再帰で計算する。
dp[0][K]が答え。