OSU

[原题](https://www.luogu.com.cn/problem/P1365) 一道不同寻常的期望$dp$题 我们定义$f_i$表示前$i$个数的答案，$g_i$表示前$i$个数的连续后缀$o$长度 可以得到转移： $$ f_i = \begin{cases} f_{i-1}+(g_{i- ......

期望 dp。 LG 传送门 自己的做法时间上过不去，且没有运用期望的优越性。 Solution 重新梳理一下思路。 首先一定要注意，求的是期望！而不是单纯的总权值。 那么对这道题，我们可以转化为：$f_i$ 表示，经过这一位之后，期望总分数增加了多少期望分。 即，若假定所求答案为 $ans_i$，输 ......