期望概率 \(dp\) 例题。
【例题 1】期望分数
设在 \(i\) 的得分是 \(x\) ，有 \(x_i\) 个连续的 \(1.\)
\[E(i)=p_i[(x_i+1)-x_i^3]+(1-p_i)E(0)+E(i-1) \]多项式乘法化简，最后得到
\[E(i-1)+p_i[3x_i^2+3x_i+1] \]问题转移到 \(E^2(x_i)\) 以及 \(E(x_i)\)
\[E^2(x_i)=p_iE(x_{i-1}+1)^2+(1-p_i)E(0)=p_i[E^2(x_{i-1})+2E(x_{i-1})+1] \]\[E(x_i)=p_i[E(x_i-1)+1] \]code
#include <bits/stdc++.h>
#define ll long long
#define db double
const int N=1e5+10;
db E[N],Ex[N],Ex2[N],p[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lf",&p[i]);
for(int i=1;i<=n;++i){
Ex[i]=p[i]*(Ex[i-1]+1);
Ex2[i]=p[i]*(Ex2[i-1]+2*Ex[i-1]+1);
E[i]=E[i-1]+p[i]*(3*Ex2[i-1]+3*Ex[i-1]+1);
}
printf("%.1lf\n",E[n]);
}