「BZOJ 4318」OSU!

题目大意：

期望的平方不等于平方的期望。

设 $x$ 表示以第 $i-1$ 位结尾的最长的连续的 $1$ 的长度，现加入第 $i$ 位的 $1$，期望得分会增加

$$\begin{eqnarray}E((x+1)^3)-E(x^3) &=&E((x+1)^3-x^3)\\ &=&E(3x^2+3x+1)\\ &=&3E(x^2)+3E(x)+1 \end{eqnarray}$$

下面是 $E(x^2)$ 的求解过程

$$\begin{eqnarray}E((x+1)^2)-E(x^2) &=&E((x+1)^2-x^2)\\ &=&E(2x+1)\\ &=&2E(x)+1 \end{eqnarray}$$

$E(x)$ 就是期望长度了。

设 $g$ 表示 $E(x)$，$h$ 表示 $E(x^2)$，$f$ 表示期望得分，转移方程见代码。

#include <cstdio>

const int N = 100005;
int n; double p[N], f[N], g[N], h[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
    for (int i = 1; i <= n; ++i) {
        g[i] = p[i] * (g[i-1] + 1);
        h[i] = p[i] * (h[i-1] + 2 * g[i-1] + 1);
        f[i] = p[i] * (f[i-1] + 3 * (h[i-1] + g[i-1]) + 1) + (1 - p[i]) * f[i-1];
    }
    printf("%.1lf", f[n]);
    return 0;
}

时间复杂度 $O(n)$