题目地址：BZOJ：Problem 4318. — OSU!

题目描述

osu 是一款群众喜闻乐见的休闲软件。
我们可以把osu的规则简化与改编成以下的样子:
一共有n次操作，每次操作只有成功与失败之分，成功对应1，失败对应0，n次操作对应为1个长度为n的01串。在这个串中连续的 X个1可以贡献X^3 的分数，这x个1不能被其他连续的1所包含（也就是极长的一串1，具体见样例解释）
现在给出n，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留1位小数。

题意简述

有一个由随机变量组成的数列，对于数列中的变量$X_i$，它的取值有$p_i$的概率为1，$1-p_i$的概率为0，一段连续的1对数列得分的贡献是该段长度的立方，一个数列的得分是所有连续的1段的贡献之和。求数列的期望分数。

输入输出格式

输入格式：
第一行有一个正整数n,表示操作个数。接下去n行每行有一个[0,1]之间的实数，表示每个操作的成功率。

输出格式：
只有一个实数，表示答案。答案四舍五入后保留1位小数。

输入输出样例

输入样例#1：

3
0.5
0.5
0.5 

输出样例#1：

6.0

说明

【样例说明】
000分数为0，001分数为1，010分数为1，100分数为1，101分数为2，110分数为8，011分数为8，111分数为27，总和为48，期望为48/8=6.0
N<=100000

题解

参考资料：BZOJ 4318 OSU! 期望DP – 世界 – CSDN博客
令随机变量$Y_i$表示到第$i$位为止连续的后缀1的期望长度，$f(i)$为到第$i$位为止总得分的期望值。加入第$i$位后，对期望的贡献值为$f(i) – f(i-1) = p_i \{\mathrm{E}[(Y_{i-1}+1)^3] – \mathrm{E}(Y_{i-1}^3)\} = p_i [3\mathrm{E}(Y_{i-1}^2) + 3\mathrm{E}(Y_{i-1}) + 1]$。
只需要维护出$Y$和$Y^2$的期望值就可以递推得到总得分的期望。
$Y$的期望分类讨论，$X_i=0$时$Y_i=0$，$X_i=1$时$Y_i=Y_{i-1}+1$，因此$\mathrm{E}(Y_i) = p_i[\mathrm{E}(Y_{i-1})+1]$。
$Y^2$的期望也可以用与上面类似的方法推，$X_i=0$时$Y^2_i=0$，$X_i=1$时$Y^2_i=(Y_{i-1}+1)^2=Y^2_{i-1} + 2Y_{i-1} + 1$，因此$\mathrm{E}(Y_i^2) = p_i[\mathrm{E}(Y^2_{i-1}) + 2\mathrm{E}(Y_{i-1}) + 1]$。
需要注意的是，$\mathrm{E}(Y^2) \neq \mathrm{E}^2(Y)$，不要犯这种低级错误。

代码

// Code by KSkun, 2019/7
#include <cstdio>

const int MAXN = 100005;

int n;
double p[MAXN], e[MAXN], e2[MAXN], dp[MAXN];

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