期望DP

因为

课程是按时间顺序的，后面的变化不会影响前面的结果

对于每个时间段的课，只有两种选择（换 or 不换）

那么

显然DP，而且 好像 转移也很好写...

显然设 dp [ i ] [ j ] 表示到了第 i 个时间段，已经提交了 j 节课的申请时的最短期望路程

写到一半发现

好像转不了...

因为不知道当前是在哪个教室，自然不知道期望路程是多少...

好像凉了..

没事，多开一维 k ，k=0表示第 i 个时间段不提交申请，k=1 表示提交申请

这样就知道在 c[ i ] 和 d[ i ] 教室上课的概率(注意是概率，因为有可能申请失败)，然后就可以知道期望路程了

设 f[ i ] 为申请第 i 节课通过的概率，dis[ i ][ j ] 为从教室 i 到教室 j 的最短路程

所以 dp [ i ] [ j ] [ 0 ] = min（dp[ i-1][ j ][ 0 ]+dis[ c[ i-1 ] ][ c[ i ] ]*1.0*1.0，

　　　　　　　　　　　　 dp[ i-1][ j ][ 1 ] + (dis[ d[ i-1] ][ c[ i ] ]*f [ i-1]*1.0) +

　　　　　　　　　　　　(dis[ c[ i-1] ][ c[ i ] ]*(1-f[ i-1])*1.0）

dis乘上的第一个数表示上一次的概率，第二个数表示这一次的概率

因为我们还不知道上一次是否申请成功，所以如果有申请就要考虑成功和失败的情况

所以期望路程就是 路程*走这条路的概率

如果没申请就肯定失败，所以期望路程就是 申请失败的路程*100%

对于 dp[ i ] [ j ] [1] 也是用类似的方法转移，但是要注意这一次也有失败的可能

所以转移会比较麻烦一些：

dp[ i ] [ j ] [ 1 ] = min（dp[ i-1][ j-1][ 0 ] + dis[ c[ i-1] ][ d[ i ] ]*1.0*f[ i ] + dis[ c[i-1] ][ c[ i ] ]*1.0*(1.0-f[ i ])，

dp[ i-1][ j-1][1] + dis[ d[ i-1 ] ][ d[ i ] ]*f[ i-1]*f[ i ] +

　　　　　　　 dis[ d[ i-1] ][ c[ i ] ]*f[ i-1]*(1.0-f[ i ]) +

　　　　　　　 dis[ c[ i-1] ][ d[ i ] ]*(1.0-f[ i-1 ])*f[ i ] +

　　　　　　　 dis[ c[ i-1] ][ c[ i ] ]*(1.0-f[ i-1])*(1.0-f[ i ]) ）

转移好像没这么简单....

好了有了转移就一点难度都没有了

预处理两点间的最短路径就用 floyd 就好了

（写这题的时候改了半天，结果是 floyd 错了...）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=2007;int n,m,t,e;int c[30007],d[20007];double dp[N][N][2],f[10007],dis[N][N];int main(){ cin>>n>>m>>t>>e; for(int i=1;i<=t;i++) for(int j=1;j
           
            0) dp[i][j][1]=min( dp[i-1][j-1][0]+dis[c[i-1]][d[i]]*1.0*f[i] + dis[c[i-1]][c[i]]*1.0*(1.0-f[i]) , dp[i-1][j-1][1]+dis[d[i-1]][d[i]]*f[i-1]*f[i] + dis[d[i-1]][c[i]]*f[i-1]*(1.0-f[i]) + dis[c[i-1]][d[i]]*(1.0-f[i-1])*f[i] + dis[c[i-1]][c[i]]*(1.0-f[i-1])*(1.0-f[i]) ); } double ans=99999999.0; for(int i=0;i<=m;i++) ans=min(ans, min(dp[n][i][0],dp[n][i][1]) ); printf("%.2lf",ans); return 0;}