求出总得分的期望值。
还没有学习数学期望的小朋友赶紧去学一下数学期望，这里只提供公式：
$E\left ( x \right )=\sum_{k=1}^{\infty }x_{k}p_{k}$
其中$x_{k}$表示对应的值，$p_{k}$表示对应的概率。
从题意中很容易看出只有O才会对答案做出贡献，设之前连续O的长度为x，则每次多出一个O造成的贡献就是$\left ( x+1 \right )^{2}-x^{2}=2*x+1$，因此我们可以用两个数组，一个是$l_{i}$，表示线性期望，另一个是$ans_{i}$，表示到i的期望得分，很容易得到
$l_{i}=\left(l_{i-1}+1\right)*p$
$ans_{i}=ans_{i-1}+\left(2*l_{i-1}+1 \right )*p$
这里显然可以空间优化，这里不多说明。
#include <cstdio> #define RI register int using namespace std; template <class T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); while(c > ‘9‘ || c < ‘0‘) { if(c == ‘-‘) f = -f; c = getchar(); } while(c >= ‘0‘ && c <= ‘9‘) { x = x * 10 + c - ‘0‘; c = getchar(); } x *= f; } int n; double l, ans, p; int main() { read(n); for(RI i = 1; i <= n; i++) { scanf("%lf", &p); ans += (l * 2 + 1) * p; l = (l + 1) * p; } printf("%lf\n", ans); return 0; }
原文：https://www.cnblogs.com/ASTiKi/p/12220682.html