首页 > 其他 > 详细

BZOJ-4318-OSU!期望DP

时间:2018-08-18 16:58:38      阅读:145      评论:0      收藏:0      [点我收藏+]

首先得了解,期望是线性的。。。但是期望的平方和立放却不是emmmmm

我们求的是x^3的期望,明摆着就是求E[X^3]的期望但是。。。E[X^3]!=E[X]^3

不如这样!!!

E[(X+1)^3]=E(X)^3+3*E[X]^2+3E[X]+1

E[(X+1)^2]=E[X]^2+2*E[X]+1;

E[X+1]=(E[X]+1)

这样岂不是美滋滋???

期望的线性性: 
期望的和=和的期望 
期望的平方≠平方的期望 
期望的立方≠立方的期望

每次如果成功,对答案贡献3*x^2+3*x+1 (接着之前的x个1) 
失败 贡献0 
我们每次计算期望长度和期望的 长度的平方,并且都要从前一位线性去推

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxx=100010;
double a[maxx];
int main(){
  int n;
  scanf("%d",&n);
  double ans=0.0;
  double x1=0.0;
  double x2=0.0,p;
  for (int i=1;i<=n;i++){
    scanf("%lf",&p);
    ans+=(1.0+x1*3.0+x2*3.0)*p;
    x2=(x2+x1*2.0+1.0)*p;
    x1=(x1+1.0)*p;
  }
  printf("%.1lf",ans);
  return 0;
}

 

BZOJ-4318-OSU!期望DP

原文:https://www.cnblogs.com/bluefly-hrbust/p/9497589.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!