题目分析

此题比第二题简单。。。考场上打了2个Dfs骗了60分 2333333

接下来讲正解

因为要使用多源的最短路径，使用Floyd初始化

数学期望的概念可以参考一下度娘：数学期望

根据数学期望的性质，可以将其线性向后递推，故使用动规

设f[i][j][0..1]表示到第i节课，用了j次换课机会，第i节课是否选择换课

方程如下：

f[i][j][0]=f[i-1][j][1]+a[i-1].probability*floyd.map[a[i-1].change][a[i].original]+(1-a[i-1].probability)*floyd.map[a[i-1].original][a[i].original];//前面一节课选择换教室，这节课不换

f[i][j][0]=fmin(f[i][j][0],f[i-1][j][0]+floyd.map[a[i-1].original][a[i].original]);//前面一节课没有换课，这节课也不选择换 

f[i][j][1]=f[i-1][j-1][0]+a[i].probability*floyd.map[a[i-1].original][a[i].change]+(1-a[i].probability)*floyd.map[a[i-1].original][a[i].original];//前面一节课没有选择换教室，这节课选择换教室

f[i][j][1]=fmin(f[i][j][1],f[i-1][j-1][1]+a[i-1].probability*(a[i].probability*floyd.map[a[i-1].change][a[i].change]+(1-a[i].probability)*floyd.map[a[i-1].change][a[i].original])+(1-a[i-1].probability)*(a[i].probability*floyd.map[a[i-1].original][a[i].change]+(1-a[i].probability)*floyd.map[a[i-1].original][a[i].original]));//前节课选择换教室，这节课也选择换教室

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=505; struct Floyd { int n; int map[maxn][maxn]; void init(int n) { this->n=n; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(i==j)map[i][j]=0; else map[i][j]=0x7fffffff/2; } void AddEdge(int from,int to,int dist) { map[from][to]=min(map[from][to],dist); } void main() { for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) map[i][j]=min(map[i][j],map[i][k]+map[k][j]); } } ; struct Plan { int original,change; double probability; } a[2005]; Floyd floyd; int Class,Apply,n,m; double f[2005][2005][2],ans=1e10; //设f[i][j][0..1]表示到第i节课，用了j次换课机会，第i节课是否选择换课 int main() { ios::sync_with_stdio(false); cin>>Class>>Apply>>n>>m; floyd.init(n); for(int i=1; i<=Class; i++)cin>>a[i].original; for(int i=1; i<=Class; i++)cin>>a[i].change; for(int i=1; i<=Class; i++)cin>>a[i].probability; for(int i=1; i<=m; i++) { int x,y,v; cin>>x>>y>>v; floyd.AddEdge(x,y,v); floyd.AddEdge(y,x,v); } floyd.main(); for(int i=1; i<=Class; i++) for(int j=0; j<=Apply; j++) f[i][j][0]=f[i][j][1]=1e10; f[1][0][0]=f[1][1][1]=0; for(int i=2; i<=Class; i++) for(int j=0; j<=Apply; j++) { f[i][j][0]=f[i-1][j][1]+a[i-1].probability*floyd.map[a[i-1].change][a[i].original]+(1-a[i-1].probability)*floyd.map[a[i-1].original][a[i].original]; //前面一节课选择换教室，这节课不换 f[i][j][0]=fmin(f[i][j][0],f[i-1][j][0]+floyd.map[a[i-1].original][a[i].original]); //前面一节课没有换课，这节课也不选择换 if(j) { f[i][j][1]=f[i-1][j-1][0]+a[i].probability*floyd.map[a[i-1].original][a[i].change]+(1-a[i].probability)*floyd.map[a[i-1].original][a[i].original]; //前面一节课没有选择换教室，这节课选择换教室 f[i][j][1]=fmin(f[i][j][1],f[i-1][j-1][1]+a[i-1].probability*(a[i].probability*floyd.map[a[i-1].change][a[i].change]+(1-a[i].probability)*floyd.map[a[i-1].change][a[i].original])+(1-a[i-1].probability)*(a[i].probability*floyd.map[a[i-1].original][a[i].change]+(1-a[i].probability)*floyd.map[a[i-1].original][a[i].original])); //前节课选择换教室，这节课也选择换教室 } } for(int i=0; i<=Apply; i++)ans=fmin(ans,min(f[Class][i][0],f[Class][i][1])); printf("%0.2lf\n",ans); return 0; }