当前位置: 首页 > >

4318: OSU! 概率与期望DP

发布时间:

因为

(x+1)3?x3=3x3+3x+1,(x+1)2?x2=2x+1

所以维护一个

3
次方的期望可以通过维护一个2次方的期望和一个

1
次方的期望,而维护一个2次方的期望可以通过维护一个

1
次方的期望。分别维护就好了。
期望的*方不等于*方的期望!


#include
#include
using namespace std;
int n;
double x,l[100005],l2[100005],f[100005];
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]+2*l[i-1]+1)*x;
f[i]=f[i-1]+(3*l2[i-1]+3*l[i-1]+1)*x;
}
printf("%.1lf
",f[n]);
return 0;
}



友情链接: