lp1654 OSU!

真是棒到不行!OSU!

首先，我们可以知道，对于长度为\(x\)的线段，在其后加上一个新的长度为1的线段，新线段的价值是\((x+1)^3\)
那么，价值的差便是：
$$3*x^2+3*x+1$$
而这样的贡献必须要当前点被选中才可行的。似乎可以得到：
$$f_{i}=f_{i-1}*(1-p_{i})+(f_{i-1}^3+3*f_{i-1}^2+3*f_{i-1}+1)*p_{i}$$
但仔细观察就可以发现这样显然是错误的。
这是因为，平方的期望不等于期望的平方。
因此，对于平方的期望，以及一次方的期望，我们应当另外维护两个函数\(g,u\)，分别表示平方的期望和一次方的期望。
那么：
$$g_{i}=(g_{i-1}+2*u_{i-1}+1)*p_{i}$$
$$u_{i}=(u_{i-1}+1)*p_{i}$$
于是：
$$f_{i}=f_{i-1}+(3*g_{i-1}+3*u_{i-1}+1)*p_{i}$$
问题得解。
这一题还是很有思维难度的。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
double p[100005],u[100005],g[100005],f[100005];
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf",&p[i]);
    }
    u[0]=g[0]=f[0]=0;
    double ans=0;
    for(int i=1;i<=n;++i){
        u[i]=(u[i-1]+1)*p[i];
        g[i]=(g[i-1]+2*u[i-1]+1)*p[i];
        f[i]=f[i-1]+(3*g[i-1]+3*u[i-1]+1)*p[i];
        ans+=f[i];
    }
    printf("%.1lf",f[n]);
    
}
int main(){
    init();
    return 0;
}