bzoj4318 OSU!

bzoj4318 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 设dp[i]表示这个串长度为i的时候我要计算的这个值的期望 首先我第i位的情况 肯定不影响i-1位之前的情况 除非他一直接过来 那么期望就可以直接先加dp[i-1]的期望 另外这个剩余的怎么算呢 假设我现在最末尾的长度为x 那么(x+1)^3-x^3 就是我新增的一部分答案 那新增的这部分答案我肯定也是要拿期望去算 预处理下e1代表最末尾长度的期望 e1代表末尾长度平方的期望 然后转移下即可

#include#define N 110000double e1[N],e2[N],dp[N],p;int n;int main(){ freopen("bzoj4318.in","r",stdin); scanf("%d",&n); for (int i=1;i<=n;++i){ scanf("%lf",&p); e1[i]=(e1[i-1]+1)*p; e2[i]=(e2[i-1]+2*e1[i-1]+1)*p; dp[i]=dp[i-1]+(3*e2[i-1]+3*e1[i-1]+1)*p; }printf("%.1f",dp[n]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。