题目内容
osu 是一款群众喜闻乐见的休闲软件。
我们可以把osu的规则简化与改编成以下的样子:
一共有 \(n(n\le100000)\) 次操作，每次操作只有成功与失败之分，成功对应1 ，失败对应0， \(n\) 次操作对应为1个长度为 \(n\) 的01串。在这个串中连续的 \(X\)个1可以贡献\(X^3\) 的分数，这\(X\)个1不能被其他连续的1所包含（也就是极长的一串1，具体见样例解释）
现在给出\(n\)，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留\(1\)位小数。
解决方案
我们假设\(f_{0,i}\)为以\(i\)结尾的连续1的长度的期望,显然,其递推公式为\(f_{0,i}=(f_{0,i-1}+1)a_i\)
而\(f_{1,i}为\)以\(i\)结尾的连续1长度的平方的期望,显然,其递推公式为\(f_{1,i}=(f_{1,i-1}+2\times f_{0,i-1}+1)a_i\)
这里可能有同学问了:为什么不能是\(f_{1,i}=f_{0,i}^2\)呢?
这是因为\(f_{1,i}\)是"长度的平方的期望"而不是"长度的期望的平方",不能直接通过\(f{2,i}\)求。
而\(f_{2,i}\)就是我们的答案,递推式是\(f_{2,i}=f_{2,i-1}+(3\times f_{1,i-1}+3\times f_{0,i-1}+1)a_i\)。
至于为什么这次\(f_{2,i-1}\)在括号外面,是因为\(f_{2,i}\)有\(1-a_i\)的概率是\(f_{2,i-1}\),而\(a_i\)的概率是\(f_{2,i-1}+3\times f_{1,i-1}+3\times f_{0,i-1}+1\)。
整理后得\(f_{2,i-1}\times(1-a_i+a_i)+a_i\times(f_{2,i-1}+3\times f_{1,i-1}+3\times f_{0,i-1}+1)\)
然后就没有然后了
代码
#include<bits/stdc++.h>
using namespace std;
#define N 100000
int n,m,i,j,ans,k;
double f[3][N+13],a[N+13];
int main()
{cin>>n;for(i=1;i<=n;i++){scanf("%lf",&a[i]);f[0][i]=(f[0][i-1]+1.0)*a[i];f[1][i]=(f[1][i-1]+2.0*f[0][i-1]+1.0)*a[i];f[2][i]=f[2][i-1]+(3.0*f[1][i-1]+3.0*f[0][i-1]+1.0)*a[i];}printf("%.1f\n",f[2][n]);
}