[BZOJ4318] OSU!

link

$solution:$

设 $g_i$ 表示以 $i$ 为末尾的极长期望长度,  $p_i$ 表示第 $i$ 个项目的成功率。

则 $g_i=(g_{i-1}+1) imes p_i$ 。

而这只能处理处 $1$ 次方的答案。

而因为 $E(x^2) eq E(x)^2$ 所以考虑再次 $dp$ 。

设 $k_i$表示以 $i$ 为末尾的极长期望长度平方,观察 $(x+1)^2=x^2+2x+1$ 得 $k_i=(k_{i-1}+2 imes g_{i-1}+1) imes p_i$。

设 $f_i$表示 $i$ 为末尾的总期望,同理得 $f_i=(f_{i-1}+3 imes k_{i-1}+3 imes g_{i-1}+1) imes p_i+f_{i-1}(1-p_i)$。

原文地址:https://www.cnblogs.com/si-rui-yang/p/10847223.html