期望的计算:如果概率为 kkk 的代价为 w1w1w1 ,概率为( 1−k1-k1−k )的代价为 w2w2w2 ，那么期望就是概率乘代价，即 kkk * w1+w1+w1+ ( 1−k1-k1−k )* w2w2w2 nnn 个时段的期望等于每个时段的期望之和，显然的. 于是我们来看这个题 首先有最短路， floyedfloyedfloyed 暴力预处理 xxx 和 yyy 之间的距离 disdisdis [ xxx ][ yyy ] 假如到 i−1i-1i−1 个时段已经走了距离 ddd ，那么有可以选择换和不换第 iii 个时段的教室 如果不换，那么显然这一时段的教室只能为 cicici 这时上一次分为换和不换两种情况，教室有 kkk [ i−1i-1i−1 ]的概率为 dididi 和( 1−k1-k1−k [ i−1i-1i−1 ])的概率为 cicici 期望按上面的算就好,教室之间的 disdisdis 乘上概率 如果换第 iii 个时段的教室，那么有 kkk [ iii ]的概率为 dididi 和( 1−k1-k1−k [ iii ])的概率为 cicici 然后上一次的同理 这个时候有 kkk [ iii ] kkk [ i−1i-1i−1 ]的概率两个教室分别为 dididi 和 ddd [ i−1i-1i−1 ] 剩下的情况同理 于是我们设 fff [ iii ][ jjj ][ kkk ]为到第 iii 个时段已经换了 jjj 个教室的期望， kkk 描述这一次换不换，为 000 换，为 111 不换 于是状态转移方程很容易写出 按照上面的描述就好 具体的可以看代码 初值， fff [ 111 ][ 111 ][ 111 ] =f=f=f [ 111 ][ 000 ][ 000 ] =0=0=0 ,其它为 infinfinf ，很好理解 答案就是 maxmaxmax { fff [ nnn ][ iii ][ kkk ]}, i=0i=0i=0 ... mmm , k=0k=0k=0 ... 111

#include<cstdio> #include<iostream> using namespace std; const int inf=1<<20;// int n,m,v,e,a[2001],b[2001],dis[2001][2001]; double ans,f[2001][2001][2],c[2001]; inline char gc()//fread加速快读 { static char BB[1000001],S=BB,T=BB; return ST&&(T=(S=BB)+fread(BB,1,1000000,stdin),ST)?EOF:S++; } inline int getin()//普通快读 { int x=0;char ch=gc(); while(ch<'0'||ch>'9')ch=gc(); while(ch>='0'&&ch<='9')x=x10+ch-48,ch=gc(); return x; } inline double rgetin()//仿照负数快读写实数快读 { double x=0;char ch=gc(); while(ch<'0'||ch>'9')ch=gc(); while(ch>='0'&&ch<='9')x=x10+(ch-48),ch=gc(); if(ch=='.') { double l=0.1; ch=gc(); while(ch>='0'&&ch<='9')x=x+(ch-48)l,l/=10,ch=gc(); } return x; } int main() { n=getin(),m=getin(),v=getin(),e=getin(); for(register int i=1;i<=n;i++)a[i]=getin();//不换的教室 for(register int i=1;i<=n;i++)b[i]=getin();//换的教室 for(register int i=1;i<=n;i++)c[i]=rgetin();//概率 for(register int i=1;i<=v;i++) for(register int j=1;j<i;j++) dis[i][j]=dis[j][i]=inf;//dis初始为inf，不用处理dis[i][i]的情况 for(register int i=1;i<=e;i++) { register int x,y,w;//从x到y有一条权值为w的边 x=getin(),y=getin(),w=getin(),dis[x][y]=dis[y][x]=min(dis[x][y],w);//无向图，防止重边 } for(register int k=1;k<=v;k++) for(register int i=1;i<=v;i++) for(register int j=1;j<i;j++)//无向图，所以不用处理j>=i if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j]; for(register int i=1;i<=n;i++) for(register int j=0;j<=m;j++) f[i][j][0]=f[i][j][1]=inf; f[1][0][0]=f[1][1][1]=0;//初始化 for(register int i=2;i<=n;i++) { register int mn=min(i,m); register double w1=dis[a[i-1]][a[i]], w2=dis[b[i-1]][a[i]]c[i-1]+dis[a[i-1]][a[i]](1-c[i-1]), w3=dis[a[i-1]][b[i]]c[i]+dis[a[i-1]][a[i]](1-c[i]), w4=dis[a[i-1]][a[i]](1-c[i-1])(1-c[i])+dis[a[i-1]][b[i]]*(1-c[i-1])c[i]+dis[b[i-1]][a[i]](1-c[i])*c[i-1]+dis[b[i-1]][b[i]]*c[i-1]*c[i];//预先算好加速，这是一个很不好看的递推式 for(register int j=0;j<=mn;j++) { f[i][j][0]=min(f[i-1][j][0]+w1,f[i-1][j][1]+w2); if(j)f[i][j][1]=min(f[i-1][j-1][0]+w3,f[i-1][j-1][1]+w4); }//正常的dp } ans=inf; for(register int i=0;i<=m;i++) ans=min(ans,min(f[n][i][0],f[n][i][1]));//统计答案 printf("%.2lf",ans); }