题意：有v个教室，e条有权无向边（保证所有教室联通）
先有n个时间段，每个时间段，牛牛（额。。）要去教室$c_i$上课
下课，他要赶到$c_{i+1}$上下一节课
目前牛牛可以申请m次，更换教室，使得下课跑的路少点
如果对时间段i申请，有$p_i$的概率成功把$c_i$换成$d_i$（失败则等于没换）
当然他也可以少申请甚至不申请
现在，求出牛牛移动距离的最小期望
输入： n，m，v，e 时间段，申请次数上限，教室数量，边
接下来三行分别为$c_i d_i p_i$
然后是边
3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
输出 2.80（两位小数）
特殊性质1:图上任意两点$a_i,b_i, a_i≠b_i$间,存在一条耗费体力最少的路径只包含一条道路。
特殊性质2:对于所有的 $1≤i≤n,k_i= 1$ 。
看到这题，明显期望DP啊。。我设的状态f[i][j]表示前i个时间段，申请了j次的距离期望。。。然而。。。。写不出来QAQ就弃坑了
最后打的暴力：dfs套dfs40分（找到所有情况）
不过，预处理是对的：Floyd处理两个教室距离
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define DB double int n; int m; int f[350][350]; int app[2050]; int huan[2050]; DB gl[2050]; bool vis[2050]; int road[550]; bool ok[2050]; int v; int e; int cnt; DB tot; double ans=0x7fffffff; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } inline void in() { freopen("classroom.in","r",stdin); freopen("classroom.out","w",stdout); } inline void out() { fclose(stdin); fclose(stdout); } inline void Floyd() { for(int k=1;k<=v;k++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) if(i!=j&&j!=k&&k!=i) f[i][j]=min(f[i][k]+f[k][j],f[i][j]); for(int i=1;i<=v;i++) f[i][i]=0; // for(int i=1;i<=n;i++) // for(int j=1;j<=n;j++) // cout<<i<<" "<<j<<" "<<f[i][j]<<endl; } inline void ddfs(int step,DB g) { if(step==n+1) { DB dis=0; for(int i=1;i<=n;i++) { if(vis[i]&&ok[i]) road[i]=huan[i]; else road[i]=app[i]; } for(int i=2;i<=n;i++) dis+=f[road[i]][road[i-1]]; tot+=dis*g; return; } if(vis[step]) { ok[step]=true; ddfs(step+1,g*gl[step]); ok[step]=false; ddfs(step+1,g*(1-gl[step])); } else ddfs(step+1,g); } inline void dfs(int step,int num,DB g) { if(step==n+1) { tot=0; ddfs(1,g); ans=min(ans,tot); return; } if(num<m) { vis[step]=true; dfs(step+1,num+1,g); vis[step]=false; } dfs(step+1,num,g); } signed main() { in(); n=read(); m=read(); v=read(); e=read(); memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++) app[i]=read(); for(int i=1;i<=n;i++) huan[i]=read(); for(int i=1;i<=n;i++) scanf("%lf",&gl[i]); for(int x,y,z,i=1;i<=e;i++) { x=read(); y=read(); z=read(); f[x][y]=f[y][x]=z; } Floyd(); dfs(1,0,1); printf("%.2lf",ans); out(); return 0; }
100分正解：（当然还是期望DP）
以dp[i][j][0/1]代表前i个教室，申请了j次，教室i有没有换
（为什么不特殊对待dp[1][1][0]和dp[1][0][1]呢？ 原因：前者可以被转移到，后者为不合法状态qaq）
先考虑不换的情况，即$k = 0$时的情况
$C1 = c[i - 1], C2 = d[i - 1], C3 = c[i], C4 = d[i]$
$mp[i][j]$表示$i,j$间的最短路
$dp[i][j][0] =minegin{cases} dp[i - 1][j][0] + mp[C1][C3]\dp[i - 1][j][1] + mp[C1][C3] * (1 - k[i - 1]) + mp[C2][C3] * k[i - 1]end{cases}$
显然如果$i-1$时没有换教室那么，$i - 1$到i只有一种情况就是都不换教室，如果$i - 1$时换了教室那么就有两种情况$i - 1$换成功了，或者没换成功所以就是对应的路径长乘上对应的概率
$dp[i][j][1] =minegin{cases} dp[i - 1][j - 1][0] + mp[C1][C3] * (1 - k[i]) + mp[C1][C4] * k[i]\dp[i - 1][j - 1][1] + mp[C2][C4] * k[i] * k[i - 1] + mp[C2][C3] * k[i - 1] * (1 - k[i]) + mp[C1][C4] * (1 - k[i - 1]) * k[i] + mp[C1][C3] * (1 - k[i - 1]) * (1 - k[i])end{cases} $
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define DB double int n; int m; int f[350][350]; int app[2050]; int huan[2050]; DB gl[2050]; double dp[2050][2050][2]; int v; int e; int cnt; DB tot; double ans=0x7fffffff; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } inline void in() { freopen("classroom.in","r",stdin); freopen("classroom.out","w",stdout); } inline void out() { fclose(stdin); fclose(stdout); } inline void Floyd() { for(int k=1;k<=v;k++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) f[i][j]=min(f[i][k]+f[k][j],f[i][j]); for(int i=1;i<=v;i++) f[i][0]=f[0][i]=f[i][i]=0; } signed main() { // in(); n=read(); m=read(); v=read(); e=read(); memset(f,60,sizeof f); memset(dp,0x5f,sizeof dp); for(int i=1;i<=n;i++) app[i]=read(); for(int i=1;i<=n;i++) huan[i]=read(); for(int i=1;i<=n;i++) scanf("%lf",&gl[i]); for(int x,y,z,i=1;i<=e;i++) { x=read(); y=read(); z=read(); f[x][y]=f[y][x]=min(f[x][y],z); } Floyd(); dp[1][0][0]=0; dp[1][1][1]=0; for(int i=2;i<=n;i++) { dp[i][0][0]=dp[i-1][0][0]+f[app[i]][app[i-1]]; for(int j=1;j<=min(m,i);j++) { dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][0]+f[app[i]][app[i-1]],dp[i-1][j][1]+f[huan[i-1]][app[i]]*gl[i-1]+f[app[i-1]][app[i]]*(1-gl[i-1]))); dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j-1][0]+f[app[i-1]][huan[i]]*gl[i]+f[app[i-1]][app[i]]*(1-gl[i]),dp[i-1][j-1][1]+f[app[i-1]][app[i]]*(1-gl[i-1])*(1-gl[i])+f[huan[i-1]][app[i]]*gl[i-1]*(1-gl[i])+f[app[i-1]][huan[i]]*(1-gl[i-1])*gl[i]+f[huan[i-1]][huan[i]]*gl[i-1]*gl[i])); } } for(int i=0;i<=m;i++) ans=min(ans,min(dp[n][i][0],dp[n][i][1])); printf("%.2lf",ans); out(); return 0; }