POJ3682 概率期望dp

掷一枚硬币，概率p正面向上，概率1-p反面朝上，现在亚瑟王要掷k次正面朝上，第i次掷硬币时花费2∗i−1。问：期望要掷多少枚硬币才能达到k次正面朝上，以及达到k次正面朝上时的花费。

---

题目链接

---

题解

• 满足几何分布，每次正面朝上的概率为 $p$，故 $k$ 次的期望为 $\frac{k}{p}$
• 定义：$f_i$:表示已经掷了 $i$ 面向上，距离$k$次正面向上还需要掷的次数
• 转移: $f_i=f_{i-1}+\frac{1}{p}$
• 定义：$g_i$: 表示已经掷了 $i$ 面向上，距离$k$次正面向上还需要掷的花费。
• 转移：$g_i=p·(g_{i+1}+2(f_{i+1}+1)-1)+(1-p)(g_i+2(f_i+1)-1)$
• 两个递推式分别转移即可