「P1850」换教室

08 / 12 / 2020 | 最后修改于 08 / 12 / 2020

OI Solution

题意

要上nn节课，每节课有对应的一个替换课程，共2n2n节课。预先所定的n节课要去的教室为 ci\large c_i ,可以通过申请以 ki\large k_i 的概率换到教室 di\large d_i , 最多申请mm次。

每次从第i−1i-1节课的教室到第ii节课的教室需要耗费 这两个教室间最短路的长度大小 的体力值。教室与教室间的路径长度题中给出,并保证任意两教室间连通。

求耗费的体力值的总和的最小期望值。

题解

典型的DP结构,考虑期望DP

预处理

发现任意两个教室之间走的方式并不影响DP过程，而且题目要求在两个教室间走的时候距离最短，于是直接用 Floyd 求出任意两个教室间的最短路（以下用disx,ydis_{x,y}表示x与y之间的最短路）

设置状态

设 f0/1,i,j\large f_{0/1,i,j} 表示考虑到第 i\large i 节课,总共已经申请过 jj 次替换,这一节课(第 ii 节)申不申请替换。

状态转移

f0,i,j=min{f0,i−1,j+disci−1,cif1,i−1,j+(1−ki−1)×disci−1,ci+ki−1×disdi−1,cif_{0,i,j}=min \begin{cases} f_{0,i-1,j}+dis_{c_{i-1},c_{i}} \\ f_{1,i-1,j}+(1-k_{i-1})\times dis_{c_{i-1},c_{i}}+k_{i-1}\times dis_{d_{i-1},c_{i}} \end{cases}

f1,i,j=min{f0,i−1,j−1+disci−1,di×ki+disci−1,ci×(1−ki)f1,i−1,j−1+ki−1×ki×disdi−1,di+(1−ki−1)×(1−ki)×disci−1,ci+ki−1×(1−ki)×disdi−1,ci+(1−ki−1)×ki×disci−1,dif_{1,i,j}=min \begin{cases} f_{0,i - 1,j - 1}+dis_{c_{i - 1},d_{i}} \times k_{i} + dis_{c_{i - 1},c_{i}} \times (1 - k_{i}) \\ f_{1,i - 1,j - 1}+k_{i - 1} \times k_{i} \times dis_{d_{i - 1},d_{i}} + (1 - k_{i - 1}) \times (1 - k_{i}) \times dis_{c_{i-1},c_{i}} + k_{i - 1} \times(1 - k_{i}) \times dis_{d_{i - 1},c_{i}} + (1 - k_{i - 1}) \times k_{i} \times dis_{c_{i - 1},d_{i}} \end{cases}