我能说这道题我想到了思路交上去只有44分，结果发现程序各种小错误，唉。。。
其实就是一个裸的概率Dp+floyed
就是转移方程烦了一点，不过也很容易想到。
用f[i][j][k]来表示前i节课选j个来换当前这节课是否要换。
具体的就看程序吧。
#include#include #include #include #define maxx 1000000000.0#define maxn 2009using namespace std;int n,m,c,e;int a[maxn][2],u1,u2,v1,v2;double d1,d2,d3,d4,g[maxn][maxn],b[maxn],f[maxn][maxn][2];int main(){ scanf("%d%d%d%d",&n,&m,&c,&e); for (int j=0;j<=1;j++) for (int i=1;i<=n;i++) scanf("%d",&a[i][j]); for (int i=1;i<=n;i++) scanf("%lf",&b[i]); for (int i=0;i<=c;i++) for (int j=0;j<=c;j++) if (i!=j) g[i][j]=maxx; int x,y,xx; for (int i=1;i<=e;i++) { scanf("%d%d%d",&x,&y,&xx); g[x][y]=min((double)xx,g[x][y]); g[y][x]=g[x][y]; } for (int k=0;k<=c;k++) for (int i=0;i<=c;i++) for (int j=0;j<=c;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) for (int k=0;k<2;k++) f[i][j][k]=maxx; f[1][0][0]=0; f[1][1][1]=0; for (int i=2;i<=n;i++) { u1=a[i][0];u2=a[i][1];v1=a[i-1][0];v2=a[i-1][1]; for (int j=0;j<=min(m,i);j++) { f[i][j][0]=f[i-1][j][0]+g[u1][v1]; if (j>0) { f[i][j][1]=f[i-1][j-1][0]+g[u1][v1]*(1-b[i])+g[u2][v1]*b[i]; f[i][j][0]=min(f[i-1][j][1]+g[u1][v1]*(1-b[i-1])+g[u1][v2]*b[i-1], f[i][j][0]); d1=g[u1][v1]*(1-b[i-1])*(1-b[i]); d2=g[u1][v2]*(1-b[i])*b[i-1]; d3=g[u2][v1]*b[i]*(1-b[i-1]); d4=g[u2][v2]*b[i]*b[i-1]; f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+d1+d2+d3+d4); } } } double ans=f[n][0][0]; for (int i=0;i<=m;i++) ans=min(min(ans,f[n][i][0]),f[n][i][1]); printf("%.2lf\n",ans); return 0;}