期望 dp。
自己的做法时间上过不去，且没有运用期望的优越性。
Solution
重新梳理一下思路。
首先一定要注意，求的是期望！而不是单纯的总权值。
那么对这道题，我们可以转化为：\(f_i\) 表示，经过这一位之后，期望总分数增加了多少期望分。
即，若假定所求答案为 \(ans_i\)，输出答案为 \(ans_n\)，那么 \(f_i=ans_{i}-ans_{i-1}\)。
那么，我们显然有 \(p_i\) 的概率，让 \(ans_{i-1}\) 加上某个值；
有 \(1-p_i\) 的概率，让 \(ans_{i-1}\) 什么也不加。
考虑第一种情况。
我们会加上多少值呢？通过大力拆分，我们拆分 \((x+1)^3-x^3\)，得到一个二次三项式。
若当前填入 \(1\)，则会比上一个答案多了 \(3x^2+3x+1\)。
有那么多种情况，如何确定 \(x\) 的值是多少呢？
这时候求期望的优越性就体现出来了。若把期望感性理解为平均值，那么我只需要线性维护 \(x^2\) 和 \(x\) 的期望（平均）值即可。
线性维护 \(x^2\) 和 \(x\) 的过程，可以理解为此题的弱化版。
综上，\(f_i=0\times (1-p_i)+(3x^2+3x+1)\times p_i\)。
那么最后 \(ans_n=\sum_{i=1}^nf_i\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn = 1e5 + 5;
typedef double db;
int n;
db p[maxn], x1[maxn], x2[maxn], f[maxn];
db ans;
int main(){
scanf("%d", &n);
rep(i, 1, n) scanf("%lf", &p[i]);
rep(i, 1, n){
x1[i] = (x1[i - 1] + 1) * p[i];
x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * p[i];
f[i] = (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * p[i];
}
rep(i, 1, n) ans += f[i];
return printf("%.1lf", ans), 0;
}
Thanks for reading.