期望概率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;
}