BZOJ 4318: OSU!

Description

osu 是一款群众喜闻乐见的休闲软件。 

我们可以把osu的规则简化与改编成以下的样子: 

一共有n次操作，每次操作只有成功与失败之分，成功对应1，失败对应0，n次操作对应为1个长度为n的01串。在这个串中连续的 X个1可以贡献X^3 的分数，这x个1不能被其他连续的1所包含（也就是极长的一串1，具体见样例解释） 

现在给出n，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留1位小数。 

Input

第一行有一个正整数n,表示操作个数。接下去n行每行有一个[0,1]之间的实数，表示每个操作的成功率。 

Output

只有一个实数，表示答案。答案四舍五入后保留1位小数。 

Sample Input

3 0.5 0.5 0.5

Sample Output

6.0

HINT

【样例说明】 

000分数为0，001分数为1，010分数为1，100分数为1，101分数为2，110分数为8，011分数为8，111分数为27，总和为48，期望为48/8=6.0 

N<=100000

Source

考虑递推，用立方差公式转移，同时要维护E(x^3)，E(x^2)，E(x)，E(1)。

考虑第i次操作，设操作前末尾最长的1长度为x。

（1）如果操作失败，贡献为0；

（2）如果操作成功，贡献为(x+1)^3 - x^3。

那么期望为(1 - pi) * 0 + pi * ((x+1)^3 - x^3)。

化简一下答案为pi * ((x+1)^3 - x^3)。

注意我们并不知道x^3具体是多少，但是我们可以算出x^3的期望是多少，而且根据期望我们知道这样算出来一定是我们想要的结果。

假设我们已经知道E(x^3)，如何计算E((x + 1)^3)？考虑递推。

E(x^3) = 0^3 * P(x = 0) + 1^3 * P(x = 1) + ... + maxl^3 * P(x = maxl)

E((x + 1)^3)  = 1^3 * P(x = 0) + 2^3 * P(x = 1) + ... + (maxl + 1)^3 * P(x = maxl)

将第二个式子用二项式定理展开，然后将第一个式子带入，可以得到

E((x + 1)^3) = E(x^3) + 3E(x^2) + 3E(x) + E(1)。

那么我们同样递推维护E(x^2)，E(x)，E(1)就好了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<vector>
 7 using namespace std;
 8 const int MAXN=100001;
 9 const int maxn=0x7fffff;
10 void read(int &n)
11 {
12     char c='+';int x=0;bool flag=0;
13     while(c<'0'||c>'9')
14     {c=getchar();if(c=='-')flag=1;}
15     while(c>='0'&&c<='9')
16     {x=x*10+c-48;c=getchar();}
17     flag==1?n=-x:n=x;
18 }
19 double f[MAXN],g[MAXN],dp[MAXN];
20 int main()
21 {
22     int n;
23     read(n);
24     for(int i=1;i<=n;i++)
25     {
26         double now;
27         scanf("%lf",&now);
28         f[i]=now*(f[i-1]+1);
29         g[i]=now*(g[i-1]+f[i-1]*2+1);
30         dp[i]=dp[i-1]+now*(g[i-1]*3+f[i-1]*3+1);
31     }
32     printf("%.1lf",dp[n]);
33     return 0;
34 }