更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19525009

前置知识

前言

既然没人讲与概率有关的知识的话，那就让我来简单介绍一下概率的相关知识吧，这个如果不知道的话这道题还是很难写的。

概率相关

定理 $1$：互补法则

定义：若事件 $A$ 发生的概率为 $P(A)$，则其不发生概率为 $1 - P(A)$。

举例：早上起来有两种选择，吃饭和不吃饭，若吃饭的概率为 $\displaystyle\frac{3}{10}$，则有不吃饭的概率为 $1 - \displaystyle\frac{3}{10} = \displaystyle\frac{7}{10}$。

定理 $2$：加法法则（互斥事件）

定义：若事件 $A_1 \sim A_n \in S$ 且 $A_i \cap A_j=\emptyset \quad \forall i, j\in\{1,2,\dots,n\},\quad i \neq j$。

那么集合中所有事件发生的概率 $P = \sum_{i=1}^n P(A_i)$。

举例：掷一次骰子时，点数大于 $4$ 的概率 $P = P(5) + P(6) = \displaystyle\frac{1}{6} + \displaystyle\frac{1}{6} = \displaystyle\frac{1}{3}$。

定理 $3$：乘法法则（无关事件）

定义：若事件 $A$ 与 $B$ 互相独立，不受影响，那么$ P(A \cap B) = P(A) \times P(B)$。

举例：早上吃饭的概率为 $\displaystyle\frac{3}{10}$，吃完饭写作业的概率为 $\displaystyle\frac{5}{6}$，那么早上吃完饭后去写作业的概率为 $\displaystyle\frac{3}{10} \times \displaystyle\frac{5}{6} = \displaystyle\frac{1}{4}$。

题目

题目大意

牛牛需要在 $n$ 个时间段内完成 $2n$ 节课程，每时间段有两节课程分别安排在教室 $c_i$ 和 $d_i$。牛牛可以申请更换教室，申请通过的概率为 $k_i$，最多申请 $m$ 次。更换教室后，牛牛需要在教室间移动，移动的体力消耗为最短路径的体力值。求最小的体力消耗期望值。

思路

题目类型

我们发现对于每一个时间段 $i$ 的课程，都有选 $c_i$ 和 $d_i$ 两种，我们可以很快想到用动态规划来解决期望概率的问题，而最短路径的话可以用弗洛伊德算法求解，因为本题 $1 \le v \le 300$，那么我们的状态如何设计呢？

状态设计

首先，对于每个时间段是一定要在状态里面的。其次，牛牛对于换教室这个事情其实是不感冒的，可以换或者不换，因此换了多少个教室是一定要在条件里面的。最后，因为我们按时间段向后 dp 的话，当前的 $i$ 时间段是由 $i - 1$ 推出的，但是无法记录上一个时间段到底换没换教室，如果要开个别的东西记录一下就太麻烦，因此就需记录上一个时间段是否换了教室。

所以我们可以这样记录状态，用 $dp_{i,j,k}$ 来表示，在第 $i$ 个时间段内，已经选了 $j$ 间教室更换，$k$ 表示当前的为这个时间段是否更换，$k \in \{0,1\}$。

转移方程（分类讨论）

一：选择不更换当前的教室，再次分类讨论。

由互补法则可知，当前成功更换的概率为 $v_i$，失败的概率即为 $1 - v_i$，而下文的 $2$ 与 $3$ 属于互斥事件，因此用加法法则，将两者的概率加到一起。

1. 前一个教室不做更改，当前期望值即为 $f_{c_{i-1},c_i}$。

2. 前一个教室做更改，且更改成功，当前期望值即为 $v_{i-1} \times f_{d_{i-1},c_i}$。

3. 前一个教室做更改，且更改失败，当前期望值即为 $(1 - v_{i-1}) \times f_{c_{i-1},c_i}$。

总结第一大类的情况，为了求最小值，所以取小，即可得出选择不更换当前教室的转移方程：

$dp_{i,j,0} \gets \min(dp_{i-1,j,0} + f_{c_{i-1},c_i},dp_{i-1,j,1} + v_{i-1} \times f_{d_{i-1},c{i}} + (1 - v_{i-1}) \times f_{c_{i-1},c_i})$

二：选择更换当前教室，再次分类讨论

下文的 $1$ 和 $2$ 属于互斥事件，而 $3,4,5,6$ 也属于互斥事件，因此用加法法则，将两者的概率加到一起。而对于 $3,4,5,6$，由乘法法则，则将两次概率相乘。

1. 前一个教室不做更改，且当前教室更改成功，当前期望值即为 $v_i \times f_{c_{i-1},d_i}$

2. 前一个教室不做更改，且当前教室更改失败，当前期望值即为 $(1 - v_i) \times f_{c_{i-1},c_i}$

3. 前一个教室做更改，且前一个更改成功，当前教室更改成功，当前期望值即为 $v_{i-1} \times v_i \times f_{d_{i-1},d_i}$

4. 前一个教室做更改，且前一个更改成功，当前教室更改失败，当前期望值即为 $v_{i-1} \times (1 - v_i) \times f_{d_{i-1},c_i}$

5. 前一个教室做更改，且前一个更改失败，当前教室更改成功，当前期望值即为 $(1 - v_{i-1}) \times v_i \times f_{c_{i-1},d_i}$

6. 前一个教室做更改，且前一个更改失败，当前教室更改失败，当前期望值即为 $(1 - v_{i-1}) \times (1 - v_i) \times f_{c_{i-1},c_i}$

总结第一大类的情况，这里的 $j$ 不要忘记 $-1$，即可得出选择更换当前教室的转移方程：

$dp_{i,j,1} \gets \min(dp_{i-1,j-1,0} + v_i \times f_{c_{i-1},d_i} + (1 - v_i) \times f_{c_{i-1},c_i},dp_{i-1,j-1,1} + v_{i-1} \times v_i \times f_{d_{i-1},d_i} + v_{i-1} \times (1 - v_i) \times f_{d_{i-1},c_i} + (1 - v_{i-1}) \times v_i \times f_{c_{i-1},d_i} + (1 - v_{i-1}) \times (1 - v_i) \times f_{c_{i-1},c_i})$