NOIp级的概率期望（然而我现在还是需要推第二遍）。
可以得到很简单的$dp$定义，$dp[i][j][0/1]$，考虑完前$i$个时间段，进行了$j$次申请，当前这次是否申请的最优期望。
剩下的转移可以直接分类讨论：
dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+p[i-1]*dis[d[i-1]][c[i]]+(1-p[i-1])*dis[c[i-1]][c[i]])，由于这一次我们没有申请，所以当上一次也没有申请的时候只有一种情况，从上个c到这个c，当上一次申请后，讨论申请是否成功，转移的距离随着是否成功而变。
dp[i][j][1]=min(dp[i-1][j-1][0]+p[i]*dis[c[i-1]][d[i]]+(1-p[i])*dis[c[i-1]][c[i]],dp[i-1][j-1][1]+p[i-1]*p[i]*dis[d[i-1]][d[i]]+p[i-1]*(1-p[i])*dis[d[i-1]][c[i]]+(1-p[i-1])*p[i]*dis[c[i-1]][d[i]]+(1-p[i-1])*(1-p[i])*dis[c[i-1]][c[i]]，式子很长，但是思想是一样的，讨论是否成功，来决定dis的下标选择。
dis数组可以直接$Floyd$解出来。
有些小细节，点数300，边数90000，明示重边，注意$Floyd$不要打丑。
最优决策$dp$注意初始化问题。
代码是最后一周写的，完全放飞自我的压行，看看$dp$式子就完事了。（注意保护眼睛）
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 inline int read(int sum=0,int f=1,char x=getchar()){ 6 while(x<'0' || x>'9'){ 7 if(x=='-') f=-1; x=getchar(); 8 }while(x>='0' && x<='9'){ 9 sum=sum*10+x-'0';x=getchar(); 10 }return sum*f; 11 } 12 13 int n,m,V,E,c[2050],d[2050],dis[305][305]; 14 double p[2050],dp[2050][2050][2],ans=1e14; 15 16 int main(){ 17 n=read(); m=read(); V=read(); E=read(); 18 for(int i=1; i<=n; ++i) c[i]=read(); for(int i=1; i<=n; ++i) d[i]=read(); for(int i=1; i<=n; ++i) scanf("%lf",p+i); 19 memset(dis,0x3f,sizeof(dis)); for(int i=1; i<=V; ++i) dis[i][i]=0; 20 for(int i=1,x,y,w; i<=E; ++i) x=read(), y=read(), w=read(), dis[x][y]=min(dis[x][y],w), dis[y][x]=min(dis[y][x],w); 21 for(int k=1; k<=V; ++k) for(int i=1; i<=V; ++i) for(int j=1; j<=V; ++j) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 22 memset(dp,88,sizeof(dp)); dp[0][0][0]=dp[0][0][1]=0; for(int i=0; i<=V; ++i) dis[i][0]=dis[0][i]=0; 23 for(int i=1; i<=n; ++i) for(int j=0; j<=min(i,m); ++j){ 24 dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+p[i-1]*dis[d[i-1]][c[i]]+(1.0-p[i-1])*dis[c[i-1]][c[i]]); 25 if(j) dp[i][j][1]=min(dp[i-1][j-1][0]+p[i]*dis[c[i-1]][d[i]]+(1.0-p[i])*dis[c[i-1]][c[i]],dp[i-1][j-1][1]+p[i-1]*p[i]*dis[d[i-1]][d[i]]+p[i-1]*(1.0-p[i])*dis[d[i-1]][c[i]]+(1.0-p[i-1])*p[i]*dis[c[i-1]][d[i]]+(1.0-p[i-1])*(1.0-p[i])*dis[c[i-1]][c[i]]); 26 } 27 for(int i=0; i<=m; ++i) ans=min(ans,min(dp[n][i][0],dp[n][i][1])); 28 printf("%.2lf",ans); return 0; 29 }