【题意】有一个长度为n的01序列，每一段极大的连续1的价值是L^3（长度L）。现在给定n个实数表示该位为1的概率，求期望总价值。n<=10^5。

【算法】期望DP

【题解】后缀长度是一个很关键的量，设g[i]表示前i个的期望后缀长度。根据全期望公式，依赖于第i-1位为0或1：（以下所有公式最后省略+(1-ai)*0）

$$g[i]=a_i*(g[i-1]+1)$$

设f[i]表示前i个的期望长度，当第i-1位为1时，f[i]相对于f[i-1]的后缀多了[ (g[i-1]+1)^3 ] - [ g[i-1]^3 ]的代价，即：

$$f[i]=f[i-1]+a_i*(3*g^2[i-1]+3*g[i-1]+1)$$

等等，这没有结束，只有加法和乘法满足期望的线性，不包括乘方。通俗地说，期望的乘方不等于乘方的期望。

设g2[i]表示前i个的期望“后缀长度的平方”，同样的g2[i]相对于g2[i-1]多了[ (g[i-1]+1)^2 ] - [ g[i-1]^2 ]，即：

$$g_2[i]=a_i*(g_2[i-1]+2*g[i-1]+1)$$

复杂度O(n)。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=100010;double f[maxn],g[maxn],g2[maxn];int n;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        double x;        scanf("%lf",&x);        g[i]=(g[i-1]+1)*x;        g2[i]=(g2[i-1]+2*g[i-1]+1)*x;        f[i]=f[i-1]+(3*g2[i-1]+3*g[i-1]+1)*x;    }    printf("%.1lf",f[n]);    return 0;}