D题 Talk 题解

/*
令f[i]表示第一次准备讲第i件事时的期望时间
则     f[i] = p[i-1]*(f[i-1]+1) + (1-p[i-1])*(f[i-1]+1 + f[i]-f[i-2])
           讲完i-1后 直接准备讲i   讲完i-1后 回到讲i-2 然后直到准备讲i   
                    
                    f[i-1]+1 为讲完事件i-1时的期望时间     
                    f[i]-f[i-2] 为回到i-2后 然后直到准备讲i 中间需要的时间         
                                                  
化简得    f[i] = (f[i-1]+1+(p[i-1]-1)*f[i-2]) / p[i-1];
初始状态  f[0] = f[1] = 0
目标      f[n+1]
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
double f[N],p[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%lf",&p[i]);
    f[0] = f[1] = 0.0;
    for(int i = 2; i <= n+1; i++){
        f[i] = (f[i-1]+1+(p[i-1]-1)*f[i-2]) / p[i-1];
    }
    printf("%.3lf",f[n+1]);
    return 0;
}