题解：P1365 WJMZBMR打osu! / Easy

显然，我们要分三种情况讨论。下面以 $f_i$ 表示 $i$ 位的得分，$x_i$ 表示 $i$ 位的连续 $o$ 数量，你可以把它们看做一个随机变量。而代码中的 $f_i$ 实际上表示 $E(f_i)$，$x_i$ 实际上表示 $E(x_i)$ 。

当前位置是 o，则有

化简得到

显然，我们还缺一个递推 $x_i$ 的式子，在这里，我们有

当前位置是 x，则有

对于以上两种情况，在求期望时直接套上一层 $E()$ 即可，不再赘述。

若当前位置是 ‘?’，那就是 x 和 o 各 $\frac{1}{2}$ 的概率。由全期望公式，加以上面的式子，我们得到

我们只需要把它们全拆开就好了，可以递推了。

需要注意的是，为什么是 $(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