https://www.luogu.org/problem/P1850
题意？太长懒得概括。
期望，记为\(E(x)\),是对于若干个概率事件，结果与概率之积的总和。
期望的数学意义是：对于一个结果均匀分布的事件，期望是无数次实验结果的平均值。
对于非均匀分布的事件，期望反映平均取值的大小。
掷骰tou子结果的平均数为3.5，这类问题说明非均匀分布事件的期望值可能不等于任何一个结果。
（以上为个人理解，可能有误，欢迎指正）
Floyd求最短路略。
首先明确，对于一个要换教室的集合，直接计算期望值是很难的。当然，可以枚举所有子集再计算，可是。。会TLE。所以考虑用递推（动态规划）的方式计算答案。
当前教室与之前教室都不换，答案为确定的距离，直接得出
\(cost=dis[c[i-1]][c[i]]\)
在当前教室i选择更换的情况下，可能成功也可能失败，则期望值是
\(cost=dis[c[i-1]][c[i]]*(1-k[i])+dis[c[i-1]][d[i]]*k[i]\)
在前一个教室选择更换的情况下，相应地有
\(cost=dis[c[i-1]][d[i]]*k[i]+dis[c[i-1]][c[i]]*(1-k[i])\)
而如果前一个教室选择更换，也相应会有两种情况。由乘法原理可以得到四种情况，相加则是
\(cost=dis[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])\)
\(+dis[c[i-1]][d[i]]*(1-k[i-1])*k[i]\)
\(+dis[d[i-1]][c[i]]*(1-k[i])*k[i-1]\)
\(+dis[d[i-1]][d[i]]*k[i-1]*k[i]\)
我们根据当前节点是否选择，将上述代价分为两组。根据题意，还有两维：当前教室和已经更换的教室数目。即
\(f[i][j][k](k\in\{0,1\})\)
表示第i个教室之前，更换了j个教室，是否更换第i个教室的最小期望代价。
综上所述，状态转移方程为
f[i][j][0]=min(f[i-1][j][1]+dis[d[i-1]][c[i]]*k[i-1]+dis[c[i-1]][c[i]]*(1-k[i-1]),f[i-1][j][0]+dis[c[i-1]][c[i]]) f[i][j][1]=min(f[i-1][j-1][0]+dis[c[i-1]][d[i]]*k[i]+dis[c[i-1]][c[i]]*(1-k[i]),f[i-1][j-1][1]+dis[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+dis[c[i-1]][d[i]]*(1-k[i-1])*k[i]+dis[d[i-1]][c[i]]*(1-k[i])*k[i-1]+dis[d[i-1]][d[i]]*k[i-1]*k[i]) //如果阅读不方便请看上文的LATEX惯例：仍然是抄的
//注：本题的状态定义为浮点数，要注意数据类型的转换 #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN=2005,MAXV=305; int n,m,v,e; int c[MAXN],d[MAXN]; double ans=1e9,k[MAXN],f[MAXN][MAXN][2],dis[MAXV][MAXV];//dis为距离 int x,y,z; int main() { scanf("%d %d %d %d",&n,&m,&v,&e); for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) dis[i][j]=1e9; for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int i=1;i<=n;i++) scanf("%lf",&k[i]); for(int i=1;i<=e;i++) { scanf("%d %d %d",&x,&y,&z); dis[y][x]=min(dis[y][x],(double)z); dis[x][y]=min(dis[x][y],(double)z);//处理重边 } for(int i=1;i<=v;i++) dis[i][i]=0;//处理自环 for(int t=1;t<=v;t++) for(int i=1;i<=v;i++) for(int j=1;j<i;j++) if(dis[i][t]+dis[t][j]<dis[i][j]) dis[i][j]=dis[j][i]=dis[i][t]+dis[t][j];//Floyd for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) f[i][j][1]=f[i][j][0]=1e9; f[1][0][0]=f[1][1][1]=0;//初始化 for(int i=2;i<=n;i++) for(int j=0;j<=m&&j<=i;j++) { f[i][j][0]=min(f[i-1][j][1]+dis[d[i-1]][c[i]]*k[i-1]+dis[c[i-1]][c[i]]*(1-k[i-1]),f[i-1][j][0]+dis[c[i-1]][c[i]]); if(j) f[i][j][1]=min(f[i-1][j-1][0]+dis[c[i-1]][d[i]]*k[i]+dis[c[i-1]][c[i]]*(1-k[i]),f[i-1][j-1][1]+dis[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+dis[c[i-1]][d[i]]*(1-k[i-1])*k[i]+dis[d[i-1]][c[i]]*(1-k[i])*k[i-1]+dis[d[i-1]][d[i]]*k[i-1]*k[i]); //状态转移 } for(int i=0;i<=m;i++) ans=min(min(ans,f[n][i][1]),f[n][i][0]);//答案更换的教室数目不确定 printf("%.2lf",ans); return 0; }最后，祝大家身体健康，再见。
转载于:https://www.cnblogs.com/ehznehc/p/11484067.html
