【noip2016】换教室 题解

题目大意

       给出一幅 v 个点的无向图，表示教室及其连边。        有 n 个时刻，每个时刻正常要到教室 c[i] 上课，如果该时刻有申请更换，则到教室 d[i] 上课。        你只能在一切开始之前提交申请，且最多申请换 m 个时刻。第 i 个时刻申请成功的概率为 k[i]。        求移动路程的期望最小值。        n,m<=2000， v<=300

对于那副图的处理

       Floyd求出任意两点最短路，然后那幅图就没用了。

dp

       一开始我设的是 f[i][j][0/1] 表示，到第 i 个时刻，已经申请了 j 次，第 i 个时刻是否换教室，的最小期望。        这样推一推就发现是错的了。因为申请与否跟最终换不换教室是两回事。

       所以应该设 f[i][j][0/1]表示，到第 i 个时刻，已经申请了 j 次，第 i 个时刻是否申请，的最小期望。        然后这样就相当于 i-1 的 0 和 1 两个点，转移到 i 的 0 和 1 两个点。总共四种转移，每种转移的期望代价就考虑一下多大概率是从 c[i-1] 来、多大概率从 d[i-1] 来，多大概率到 c[i] 去、多大概率到 d[i] 去，然后相应地乘上最短路即可。

告诉我v、n打反的不止我一个

       T^T        QAQ

代码

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; typedef long long LL; const int maxn=2005, maxv=305; const LL inf=1e11; int n,m,v,e,rm[maxn][2]; double k[maxn]; int dis[maxv][maxv]; void Floyd() { fo(k,1,v) fo(i,1,v) if (i!=k && dis[i][k]<dis[0][0]) fo(j,1,v) if (j!=i && j!=k && dis[k][j]<dis[0][0] && dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; } double Min(double x,double y) { if (x>inf && y>inf) return inf; if (x>inf) return y; if (y>inf) return x; if (x<y) return x; else return y; } double f[maxn][maxn][2]; int main() { freopen("classroom.in","r",stdin); freopen("classroom.out","w",stdout); scanf("%d %d %d %d",&n,&m,&v,&e); fo(i,1,n) scanf("%d",&rm[i][0]); fo(i,1,n) scanf("%d",&rm[i][1]); fo(i,1,n) scanf("%lf",&k[i]); memset(dis,127,sizeof(dis)); fo(i,1,e) { int x,y,w; scanf("%d %d %d",&x,&y,&w); dis[x][y]=min(dis[x][y],w); dis[y][x]=min(dis[y][x],w); } fo(i,1,v) dis[i][i]=0; Floyd(); fo(i,1,n) fo(j,0,m) fo(c,0,1) f[i][j][c]=inf; f[1][0][0]=f[1][1][1]=0; fo(i,2,n) fo(j,0,m) fo(c,0,1) { double t=k[i-1]*dis[rm[i-1][1]][rm[i][0]]+(1-k[i-1])*dis[rm[i-1][0]][rm[i][0]]; f[i][j][0]=Min(f[i-1][j][0]+dis[rm[i-1][0]][rm[i][0]],f[i-1][j][1]+t); if (j) { double t1=k[i]*dis[rm[i-1][0]][rm[i][1]]+(1-k[i])*dis[rm[i-1][0]][rm[i][0]]; t=k[i-1]*k[i]*dis[rm[i-1][1]][rm[i][1]]+(1-k[i-1])*k[i]*dis[rm[i-1][0]][rm[i][1]]; t+=k[i-1]*(1-k[i])*dis[rm[i-1][1]][rm[i][0]]+(1-k[i-1])*(1-k[i])*dis[rm[i-1][0]][rm[i][0]]; f[i][j][1]=Min(f[i-1][j-1][0]+t1,f[i-1][j-1][1]+t); } } double ans=inf; fo(j,0,m) ans=min(ans,Min(f[n][j][0],f[n][j][1])); printf("%.2f\n",ans); }