标签：期望 times 3E 答案 长度 导航 金牌 DP

期望概率DP

例题A题解

首先，对于随机变量 \(X\)
如果设随机变量 \(Y\) 的取值集合是 \(I(Y)\)，那么有全期望公式

\[E(X)=\sum_{y\in I(Y)}E(X|Y=y)\times P(Y=y) \]

其中，\(E(X|Y=y)\) 表示在 \(Y=y\) 的条件下 \(X\) 的期望取值。
对于这道题，长度增加一对答案的贡献是 \(3E^2(x)+3E(x)+1\)，其中 \(E^2(x)\) 与 \(E(x)\) 分别表示长度平方的期望和长度的期望。
但是期望没有乘法，也就是说，\(E(x)\times E(x)=E^2(x)\) 不成立。
那怎么办呢？
不难发现，长度增加一对长度平方的贡献是 \(2x+1\)。
总结一下，如果设第 \(x\) 位成功的概率是 \(P(x)\)，那么有：

\[E(x)=(E(x-1)+1)\times P(x)\\ E^2(x)=P(x)\times (E^2((x-1))+2\times E(x-1) + 1) + (1 - P(x))\times 0 \]

那么这一位对答案的贡献就是

\[ans=ans+P(x)\times (3E^2(x)+3E(x)+1) \]

question：为什么不用上面的方法更新答案？
answer：其实你求的长度平方期望和长度期望从某种意义上说，其实是到这一位为止连续的长度的期望，如果用上文的方法更新答案，答案的意义就变成了到最后一位为止连续的长度的三次方的期望，当然不是答案啦！

例题A代码

#include<bits/stdc++.h>
using namespace std;
int n;double p, pow3, pow1, pow2;
signed main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        scanf("%lf",&p);
        pow3 += (3.0 * pow2 + 3.0 * pow1 + 1.0) * p;
        pow2 = (pow2 + 2.0 * pow1 + 1.0) * p;
        pow1 = (pow1 + 1.0) * p;
    }
    printf("%.1lf\n",pow3);
    return 0;
}

标签：期望,times,3E,答案,长度,导航,金牌,DP
From： https://www.cnblogs.com/Call-me-Eric/p/17914524.html