【题目链接】:http://codeforces.com/problemset/problem/235/B

【题意】



让你玩一个游戏,游戏结果由一个长度为n的01字符组成;

这个结果的分数与连续的1的个数对应;

对于每一个“1”的连续块,假设长度为L;

为0的部分不计分

则总分加上L 2  

然后告诉你每个位置有p[i]的可能性为1;1-p[i]的可能性为0;

问你最后的期望得分是多少;

【题解】



这个规则能够写成另外一种形式;

1.

如果两个1所在的位置为i和j;

且i和j之间没有0

则分数递增2

2.

每一个1,答案递增1;

原理:

2∗C(n,2)+n=n 2  

这样,我们只要枚举新加的一位是1的时候的可能情况就好;

->在第i位新加的1个1使得连续1的个数变为2、3、4..i(i>1)

对于长度为2的

答案递增2*p[i]*p[i-1];

对于长度为3的

答案递增2*p[i]*p[i-1]*p[i-2]…

我们能够写出dp方程;

设(i,j)为dp[i]*dp[i+1]..*dp[j];

dp[i]表示

∑(j,i) 

这里j< i

则有dp[i] = (dp[i-1]+p[i-1])*p[i];

然后对于每个i;

答案累加2*dp[i];

这样就能算出,以第i个位置为某个连续”1”块的最后一个位置,这个位置为1对答案的贡献了;

把每个位置为1的贡献都加起来;

最后再加上,每个位置为1的贡献都为1.(即∑p[i]);

就是最后的期望了.



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("D:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1e5+100;

const int INF = 0x3f3f3f3f;

int n;

double p[N],ans = 0,dp[N];

int main(){

    //Open();

    Close();//scanf,puts,printf not use

    //init??????

    cin >> n;

    rep1(i,1,n){

        cin >> p[i];

        ans+=p[i];

    }

    dp[0] = dp[1] = 0;

    rep1(i,2,n){

        dp[i] = (dp[i-1]+p[i-1])*p[i];

        ans+=2*dp[i];

    }

    cout << fixed << setprecision(10)<<ans<<endl;

    return 0;

}