期望的计算:如果概率为 kkk 的代价为 w1w1w1 ,概率为( 1−k1-k1−k )的代价为 w2w2w2 ，那么期望就是概率乘代价，即 kkk * w1+w1+w1+ ( 1−k1-k1−k )* w2w2w2 nnn 个时段的期望等于每个时段的期望之和，显然的. 于是我们来看这个题 首先有最短路， floyedfloyedfloyed 暴力预处理 xxx 和 yyy 之间的距离 disdisdis [ xxx ][ yyy ] 假如到 i−1i-1i−1 个时段已经走了距离 ddd ，那么有可以选择换和不换第 iii 个时段的教室 如果不换，那么显然这一时段的教室只能为 cicici 这时上一次分为换和不换两种情况，教室有 kkk [ i−1i-1i−1 ]的概率为 dididi 和( 1−k1-k1−k [ i−1i-1i−1 ])的概率为 cicici 期望按上面的算就好,教室之间的 disdisdis 乘上概率 如果换第 iii 个时段的教室，那么有 kkk [ iii ]的概率为 dididi 和( 1−k1-k1−k [ iii ])的概率为 cicici 然后上一次的同理 这个时候有 kkk [ iii ] kkk [ i−1i-1i−1 ]的概率两个教室分别为 dididi 和 ddd [ i−1i-1i−1 ] 剩下的情况同理 于是我们设 fff [ iii ][ jjj ][ kkk ]为到第 iii 个时段已经换了 jjj 个教室的期望， kkk 描述这一次换不换，为 000 换，为 111 不换 于是状态转移方程很容易写出 按照上面的描述就好 具体的可以看代码 初值， fff [ 111 ][ 111 ][ 111 ] =f=f=f [ 111 ][ 000 ][ 000 ] =0=0=0 ,其它为 infinfinf ，很好理解 答案就是 maxmaxmax { fff [ nnn ][ iii ][ kkk ]}, i=0i=0i=0 ... mmm , k=0k=0k=0 ... 111