数学期望
万弘
·
·
个人记录
数学期望
其实我也不是很会
定义:
在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。
说人话:定义E为期望,E_i为事件i的结果(值),P_i为事件i的发生概率,则有
E=\sum E_i*P_i
简单例题:似乎并没有简单例题
例1:换教室
期望dp.
设f[0/1][i][j]表示考虑前i个课程,申请了j次的最小期望,且这一次没有/有申请的最小期望值
设dis[u][v]表示u到v的最短距离(显然可以Floyd求出)
如果不申请,必定失败.否则有k_i的几率成功,1-k_i的几率失败(注意前一次申请也是可能失败的)
f[0][i][j]=min(f[0][i-1][j],min(f[1][i-1][j]+k[i-1]*dis[b[i-1]][a[i]]+(1-k[i-1])*dis[a[i-1]][a[i]])
```cpp
/**********/
#define MAXN 2011
ll n,m,v,e;
ll a[MAXN],b[MAXN],dis[MAXN][MAXN];
double k[MAXN];
double f[2][MAXN][MAXN];//f[op][i][j]:in[1,i],change j times,and i is(not)changed.
void Floyd()
{
for(ll k=1;k<=v;++k)
for(ll i=1;i<=v;++i)
for(ll j=1;j<=v;++j)
umin(dis[i][j],dis[i][k]+dis[k][j]);
}
int main()
{
memset(dis,0x3f,sizeof dis);
n=read(),m=read(),v=read(),e=read();
for(ll i=1;i<=n;++i)a[i]=read();
for(ll i=1;i<=n;++i)b[i]=read();
for(ll i=1;i<=n;++i)scanf("%lf",&k[i]);
for(ll i=1;i<=v;++i)dis[i][i]=0;
for(ll i=1;i<=e;++i)
{
ll u=read(),v=read(),w=read();
umin(dis[u][v],w);umin(dis[v][u],w);
}
Floyd();
for(ll i=0;i<=n;++i)
for(ll j=0;j<=m;++j)
f[0][i][j]=f[1][i][j]=1e20;
f[0][1][0]=0,f[1][1][1]=0;
for(ll i=2;i<=n;++i)
{
f[0][i][0]=f[0][i-1][0]+dis[a[i-1]][a[i]];
for(ll j=1;j<=min(i,m);++j)
{
f[0][i][j]=std::min(
f[0][i-1][j]+dis[a[i-1]][a[i]],
f[1][i-1][j]+k[i-1]*dis[b[i-1]][a[i]]+(1-k[i-1])*dis[a[i-1]][a[i]]
);
f[1][i][j]=std::min(
f[0][i-1][j-1]+k[i]*dis[a[i-1]][b[i]]+(1-k[i])*dis[a[i-1]][a[i]],
f[1][i-1][j-1]+
k[i-1]*k[i]*dis[b[i-1]][b[i]]+
k[i-1]*(1-k[i])*dis[b[i-1]][a[i]]+
(1-k[i-1])*k[i]*dis[a[i-1]][b[i]]+
(1-k[i-1])*(1-k[i])*dis[a[i-1]][a[i]]
);
}
}
double ans=1e20;
for(ll j=0;j<=m;++j)ans=std::min(ans,std::min(f[0][n][j],f[1][n][j]));
printf("%.2lf",ans);
return 0;
}
```