正題

---

題目大意

一張圖，$n$次，每次在$c_i$上課，可以申請換課室到$d_i$，成功概率$k_i$。求最短需要走的路徑的期望長度

---

解題思路

先$Flody$預處理多源最短路，然后考慮$dp$

設$f_{i,j,0/1}$表示前$i$次，已經申請了$j$次，這次是否申請了，的最短期望長度。

為了方便我們定義$lc=c_{i?1},ld=d_{i?1},nc=c_i,nd=d_i$

$$f_{i,j,0}=\{\begin{array}{cc}{f}_{i?1,j,0}+di{s}_{lc,nc}& \\ f_{i?1,j,1}+k_{i?1}?di{s}_{ld,nc}+(1?k_{i?1})?di{s}_{lc,nc}& \end{array}$$

而
$$f_{i,j,1}=\{\begin{array}{cc}{f}_{i?1,j?1,0}+k_i?di{s}_{lc,nd}+(1?k_i)?di{s}_{lc,nc}& \\ f_{i?1,j?1,1}+k_{i?1}?k_i?di{s}_{ld,nd}+(1?k_{i?1})?k_i?di{s}_{lc,nd}+k_{i?1}?(1?k_i)?disldnc+(1?k_{i?1})?(1?k_i)?di{s}_{lc,nc}& \end{array}$$

---

$code$

#include<cstdio> #include<algorithm> using namespace std; const int N=2010; int n,m,v,e,c[N],d[N],dis[N][N]; double k[N],f[N][N][2],mins; int main() {freopen("testdata.in","r",stdin);scanf("%d%d%d%d",&n,&m,&v,&e);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<=v;i++)for(int j=1;j<=v;j++)dis[i][j]=2147483647/3;for(int i=1;i<=e;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);dis[x][y]=dis[y][x]=min(dis[x][y],w);}for(int ks=1;ks<=v;ks++){dis[ks][ks]=0;for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)if(dis[i][ks]+dis[ks][j]<dis[i][j])dis[i][j]=dis[i][ks]+dis[ks][j];}for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)f[i][j][0]=f[i][j][1]=2147483647/3;f[1][1][1]=f[1][0][0]=0;for(int i=2;i<=n;i++){for(int j=0;j<=min(i,m);j++){f[i][j][0]=min(f[i-1][j][0]+dis[c[i-1]][c[i]],f[i-1][j][1]+k[i-1]*dis[d[i-1]][c[i]]+(1-k[i-1])*dis[c[i-1]][c[i]]);if(j){f[i][j][1]=min(f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]],f[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]]);}}}mins=2147483647;if(n==1) mins=0;for(int j=0;j<=m;j++)mins=min(mins,min(f[n][j][0],f[n][j][1]));printf("%0.2lf",mins); }

總結

以上是生活随笔為你收集整理的P1850-换教室【数学期望,dp,Floyd】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。