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

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

期望DP~

和3450是一样的，只不过这个是三次的所以要多记录一个l[i]^2 的期望值~

如果前后都是1，那么这个1对答案的贡献就是3*l^2+3*l+1；

用f[i]表示到第i位时的最大值，那么f[i]=f[i-1]+(3*l2[i]+3*l[i]+1)*a[i]；

而l[i]记录的是到第i位时的期望1串长度，那么l[i]=(l[i-1]+1)*a[i]；

l2[i]记录的是到第i位时的期望1串长度的平方，那么l2[i]=(l2[i-1]+l[i-1]*2+1)*a[i]。

（刚开始写出来是6.1还以为是精度误差结果居然是方程写错了……2333）

#include<cstdio> int n; double x,l[100001],l2[100001],f[100001]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lf",&x); l[i]=(l[i-1]+1)*x; l2[i]=(l2[i-1]+l[i-1]*2+1)*x; f[i]=f[i-1]+(3*l2[i-1]+3*l[i-1]+1)*x; } printf("%.1lf\n",f[n]); return 0; }