假设{ Bn | n = 1, 2, 3, ... } 是一个概率空间的有限或者可数无限的分割，且每 个集合 Bn 是一个可测集合，则对任意事件 A 有全概率公式：
一下来自 贼清晰！简直是一朵清奇的白莲花
- f[i][j][0/1]表示前i个时间点，共申请了j次，第i个时间点否/是进行了申请。
- dis[a][b]表示a教室->b教室的距离
- c[i]表示默认的教室
- d[i]表示更换后的教室
- k[i]表示第i个教室申请成功的概率
分类讨论主要分成两大类，4小类，最后分成9个小项进行考虑。
-
一、当前教室没有申请
-
如果前一教室有申请： f[i][j][0]=min(f[i−1][j][1]f[i][j][0]=min(f[i-1][j][1]f[i][j][0]=min(f[i−1][j][1]
- （1）成功：+k[i−1]∗dis[d[i−1]][c[i]]+k[i-1]*dis[d[i-1]][c[i]]+k[i−1]∗dis[d[i−1]][c[i]]
- （2）失败：+(1−k[i−1])∗dis[c[i−1]][c[i]]+(1-k[i-1])*dis[c[i-1]][c[i]]+(1−k[i−1])∗dis[c[i−1]][c[i]]
- 如果前一教室没有申请：,f[i−1][j][0],f[i-1][j][0],f[i−1][j][0],一定是前后均失败：+dis[c[i−1]][c[i]])+dis[c[i-1]][c[i]])+dis[c[i−1]][c[i]])
-
- 二、当前教室有申请
- 如果前一教室有申请：f[i][j][1]=min(f[i−1][j−1][1]f[i][j][1]=min(f[i-1][j-1][1]f[i][j][1]=min(f[i−1][j−1][1]
- （1）前后均成功：+k[i−1]∗k[i]∗dis[d[i−1]][d[i]]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+k[i−1]∗k[i]∗dis[d[i−1]][d[i]]
- （2）前成功、后失败：+k[i−1]∗(1−k[i])∗dis[d[i−1]][c[i]]+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+k[i−1]∗(1−k[i])∗dis[d[i−1]][c[i]]
- （3）前失败、后成功：+(1−k[i−1])∗k[i]∗dis[c[i−1]][d[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+(1−k[i−1])∗k[i]∗dis[c[i−1]][d[i]]
- （4）前后均失败：+(1−k[i−1])∗(1−k[i])∗dis[c[i−1]][c[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]]+(1−k[i−1])∗(1−k[i])∗dis[c[i−1]][c[i]]
- 如果前一教室没有申请：,f[i−1][j−1][0],f[i-1][j-1][0],f[i−1][j−1][0]
- （1）后成功：+k[i]∗dis[c[i−1]][d[i]]+k[i]*dis[c[i-1]][d[i]]+k[i]∗dis[c[i−1]][d[i]]
- （2）后失败：+(1−k[i])∗dis[c[i−1]][c[i]])+(1-k[i])*dis[c[i-1]][c[i]])+(1−k[i])∗dis[c[i−1]][c[i]])
代码
1 /* 2 id:gww 3 language：C-- 4 5 */ 6 #include<bits/stdc++.h> 7 using namespace std; 8 const int inf=0x3f3f3f3f; 9 const int N=2000+100,V=300+100; 10 int n,m,v,e; 11 int c[N],d[N],co[V][V]; 12 //教室 可换教室 消耗体力值 13 double k[N],f[N][N][2],ans=inf; 14 inline int rd() 15 { 16 int x=0,w=0;char ch=0; 17 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 18 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 19 return w?-x:x; 20 } 21 22 23 void Floyd()//处理出任意教室之间消耗最小体力值 24 { 25 for (int kk=1;kk<=v;kk++)//中转点 26 for (int a=1;a<=v;a++) 27 for (int b=1;b<a;b++) 28 if (co[a][b]>co[a][kk]+co[kk][b]) 29 co[b][a]=co[a][b]=co[a][kk]+co[kk][b]; 30 } 31 32 void lxy() 33 { 34 for (int i=2;i<=n;i++)//时间段 35 for (int j=0;j<=m;j++)//申请数 36 { 37 double a=k[i-1],b=k[i]; 38 int x=co[d[i-1]][c[i]],y=co[d[i-1]][d[i]],z=co[c[i-1]][c[i]],w=co[c[i-1]][d[i]]; 39 //前1后0 前后均成功 前后均失败 前0后1 40 f[i][j][0]= min(f[i-1][j][1]+a*x+ (1-a)*z, f[i-1][j][0] +z);//当前时间未申请 41 if(j)//当前时间段申请了 42 f[i][j][1]=min(f[i-1][j-1][0]+b*w+(1-b)*z,f[i-1][j-1][1]+a*b*y+a*(1-k[i])*x+(1-a)*b*w+(1-a)*(1-b)*z); 43 // 前一段未申请 前一段申请了 44 } 45 } 46 47 int main() 48 { 49 //memset(dis,inf,sizeof(dis));//初始化赋极大值 50 n=rd(),m=rd(),v=rd(),e=rd(); 51 for (int i=1;i<=n;i++) c[i]=rd(); 52 for (int i=1;i<=n;i++) d[i]=rd(); 53 for (int i=1;i<=n;i++) scanf("%lf",&k[i]); 54 for (int i=1;i<=v;i++) 55 for (int j=1;j<i;j++) 56 co[j][i]=co[i][j]=inf; 57 for (int i=1;i<=e;i++) 58 { 59 int x=rd(),y=rd(),w=rd(); 60 co[x][y]=co[y][x]=min(co[x][y],w); 61 } 62 Floyd(); 63 for (int i=1;i<=n;i++) 64 for (int j=0;j<=m;j++) 65 f[i][j][0]=f[i][j][1]=inf; 66 f[1][0][0]=0;f[1][1][1]=0;//初始化 67 lxy(); 68 for (int i=0;i<=m;i++) 69 ans=min(ans,min(f[n][i][1],f[n][i][0])); 70 printf("%.2lf",ans); 71 return 0; 72 }