题解 P1850 【换教室】

### 【题目】   ### 【声明】 - 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]$ - （1）成功：$+k[i-1]*dis[d[i-1]][c[i]]$ - （2）失败：$+(1-k[i-1])*dis[c[i-1]][c[i]]$ - 如果前一教室没有申请：$,f[i-1][j][0]$,一定是前后均失败：$+dis[c[i-1]][c[i]])$ ------------ - 二、当前教室有申请 - 如果前一教室有申请：$f[i][j][1]=min(f[i-1][j-1][1]$ - （1）前后均成功：$+k[i-1]*k[i]*dis[d[i-1]][d[i]]$ - （2）前成功、后失败：$+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]]$ - （4）前后均失败：$+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]]$ - 如果前一教室没有申请：$,f[i-1][j-1][0]$ - （1）后成功：$+k[i]*dis[c[i-1]][d[i]]$ - （2）后失败：$+(1-k[i])*dis[c[i-1]][c[i]])$ - 总结出来的动态转移方程式是： ```cpp f[i][j][0]= min(f[i-1][j][1]+ k[i-1]*dis[d[i-1]][c[i]]+ (1-k[i-1])*dis[c[i-1]][c[i]] , f[i-1][j][0] +dis[c[i-1]][c[i]]); ``` ```cpp f[i][j][1]=min(f[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]] , f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]]) ``` ### 【解题反思】 - 做这题的时候发现推出来的公式很优秀，程序的Floyd和DP部分也很优秀，但是却总是错样例。结果发现是Floyd初始化的时候把x->x也赋值为了无穷大，gg。毕竟我很久没用Floyd，细节大半都忘记了……这题当做算是回忆起来一些细节了吧！ ### 【参考程序】 ```cpp #include<cstdio> #include<iostream> using namespace std; const int INF=800000000; int n,m,v,e; int c[2005],d[2005],dis[305][305]; double k[2005],f[2005][2005][2]; void Read() { 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<i;j++) dis[j][i]=dis[i][j]=INF; for (int i=1;i<=e;i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); dis[a][b]=min(dis[a][b],w); dis[b][a]=dis[a][b]; } } void Floyd() { for (int k=1;k<=v;k++) for (int i=1;i<=v;i++) for (int j=1;j<i;j++) if (dis[i][j]>dis[i][k]+dis[k][j]) dis[j][i]=dis[i][j]=dis[i][k]+dis[k][j]; } void DP() { for (int i=1;i<=n;i++) for (int j=0;j<=m;j++) { f[i][j][0]=f[i][j][1]=INF; } f[1][0][0]=0; f[1][1][1]=0; for (int i=2;i<=n;i++) for (int j=0;j<=m;j++) { f[i][j][0]= min(f[i-1][j][1]+ k[i-1]*dis[d[i-1]][c[i]]+ (1-k[i-1])*dis[c[i-1]][c[i]], f[i-1][j][0] +dis[c[i-1]][c[i]]); if (j!=0) f[i][j][1]=min(f[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]], f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]]); } } void Write() { double ans=INF; for (int i=0;i<=m;i++) for (int j=0;j<=1;j++) { ans=min(ans,f[n][i][j]); } printf("%.2lf",ans); } int main() { Read(); Floyd(); DP(); Write(); return 0; } ```