题解：P1365 WJMZBMR打osu! / Easy
Nagato_
·
·
题解
显然，我们要分三种情况讨论。下面以 f_i 表示
**当前位置是 o**，则有
$$f_i=f_{i-1}+(x_{i-1}+1)^2-x_{i-1}^2$$
化简得到
$$f_i=f_{i-1}+2x_{i-1}+1$$
显然，我们还缺一个递推 $x_i$ 的式子，在这里，我们有
$$x_i=x_{i-1}+1$$
**当前位置是 x**，则有
$$
f_i=f_{i-1}\\
x_i=0
$$
对于以上两种情况，在求期望时直接套上一层 $E()$ 即可，不再赘述。
若当前位置是 ‘?’，那就是 x 和 o 各 $\frac{1}{2}$ 的概率。由全期望公式，加以上面的式子，我们得到
$$
E(x_i)=\frac{1}{2}E(x_{i-1}+1)\\
E(f_i)=\frac{1}{2} E(f_{i-1}+2x_{i-1}+1) + \frac{1}{2} E(f_{i-1})
$$
我们只需要把它们全拆开就好了，可以递推了。
需要注意的是，为什么是 $(x_{i-1}+1)^2$ 而不是 $x_i^2$ 。我们发现，当这一位是 ‘?’ 时，有 $\frac{1}{2}$ 的可能，这一位是 o ，而在这种情况下，得分一定满足 $f_i=f_{i-1}+(x_{i-1}+1)^2-x_{i-1}^2$ ，如果我们用 $x_i$ ，就会受到选 x 的概率的干扰。而在递推下一位时，下一位确实可能受到这一位选 x 的影响。
以此纪念第一道概率dp