不说闲话
概率和期望一直是自己非常薄弱的板块，最早学的时候其实就没有完全听懂。
导致打模拟赛，甚至是 ABC 的时候遇到概率期望相关的题基本上都是绕道走，有时候暴力都打不出来。
重修一下概率论，接下来是做题笔记，后面也会整理成讲题。
P1365 WJMZBMR打osu! / Easy
期望入门题。
题目大意
有一个长度为 #N# 的字符串，由 o，x 和 ? 组成。
定义总分数为：字符串中每一段最长连续 o 字串长度的平方和。
? 的含义是该字符不确定，是 o 或 x，各有 \(50 \%\) 的可能性。
求总分数的期望值。
解题思路
很容易想到 dp。
- 设 \(f_i\) 表示前 \(i\) 个字符分数的期望值；
- 设 \(g_i\) 表示前 \(i\) 个字符中以 \(i\) 为最后一个字符的连续
o字串的期望长度。
接下来就可以分类讨论进行状态转移：
\( \begin{cases} s_i=o \begin{cases} f_i= f_{i-1}+ 2\times g_{i-1} +1 \\ g_i=g_{i-1}+1 \end{cases}\\ \\ s_i=x \begin{cases} f_i= f_{i-1} \\ g_i=0 \\ \end{cases}\\ \\ s_i=?\ \ \begin{cases} f_i=f_{i-1}+g_{i-1}+0.5 \\ g_i=0.5\times g_{i-1} + 0.5 \end{cases}\\ \end{cases} \)
时间复杂度 \(O(N)\)
标签：begin,概率,end,0.5,萌新,期望,cases From： https://www.cnblogs.com/Sunbutstfan1106/p/18675757