博尔塔拉蒙古自治州网站建设_网站建设公司_门户网站_seo优化

概率 DP

存档一些概率 / 期望 DP 的好题，我会持续更新

一、数学概念初步

概率的基本性质

互斥事件的性质

若 \(A\) 与 \(B\) 互为互斥事件，则

\[P(A\cup B)=P(A)+P(B) \]

对立事件的性质

若 \(A\) 与 \(B\) 互为对立事件，则

\[\begin{cases} P(A) = 1 - P(B) \\ P(B) = 1 - P(A) \end{cases} \]

广义容斥原理在概率论中的应用

若 \(A\) 与 \(B\) 为同一试验中的两个事件，则

\[P(A\cup B) = P(A) + P(B) - P(A\cap B) \]

独立事件的性质

若事件 \(A\) 与 \(B\) 相互独立，则

\[P(AB) = P(A)\times P(B) \]

值得注意的是，这里高中文化课是反过来定义的，即声称满足上式的两个事件相互独立。

期望

概念

若离散型随机变量 \(X\) 的分布列满足下表

\(X\)	\(P(X)\)
\(x_1\)	\(p_1\)
\(x_2\)	\(p_2\)
\(\cdots\)	\(\cdots\)
\(x_n\)	\(p_n\)

则规定 \(X\) 的期望为

\[E(X) = \sum_{i = 1}^{n}x_ip_i \]

即期望是试验中每次可能结果的概率乘以其结果的总和。

通过上式可见，期望反映了随机变量平均取值的大小。可以粗略理解为随机变量的平均值。

需要注意的是，期望值并不一定等同于常识中的“期望”，即期望值也许与每一个结果都不相等。期望值是该变量输出值的平均数，而并不一定包含于变量的输出值集合里。

期望的线性性

如果 \(X\) 和 \(Y\) 是两个随机变量，那么有

\[E(X + Y) = E(X) + E(Y) \]

容易感性理解：随机变量之和的期望，恰等于随机变量期望的和。

证明如下

\[\begin{aligned} E(X + Y) &= \sum_x\sum_y (x + y)P(X=x,Y=y) \\&= \sum_x\sum_y x P(X=x,Y=y) + \sum_x\sum_y y P(X=x,Y=y) \\&= \sum_x x \sum_y P(X=x,Y=y) + \sum_y y \sum_x P(X=x,Y=y) \\&= \sum_x P(X=x) + \sum_y P(Y=y) \\&= E(X)+E(Y) \end{aligned} \]

这个证明的精髓主要在将和式展开的部分。

二、例题

CF148D Bag of mice

定义 \(f_{i, j}\) 表示袋子里剩 \(i\) 个白鼠，\(j\) 个黑鼠，先手胜的概率。

因为先手获胜，当且仅当先手抓出来白老鼠，所以显然有 \(f_{0, j} = 0\)，\(f_{i, 0} = 1\)。

记 \(p\) 为事件发生的概率。下面考虑转移。

1. 如果先手抓到白鼠，那么获胜。

   \[\]
   \[ \]
   \[\]
   \[ \]

   先手抓到黑鼠、后手抓到白鼠的概率为 \(\dfrac{j}{i + j} \cdot \dfrac{j - 1}{i + j - 1}\)。设这个值为 \(Q\)。以下分类讨论：

   1. 跑出来的是白鼠

\[p = Q \cdot \frac {i} {i + j - 2} \cdot f_{i - 1, j - 2} \]

​ 2) 跑出来的是黑鼠

\[p = Q \cdot \frac {j - 2} {i + j - 2} \cdot f_{i,j - 3} \]

综上

\[f_{i,j} = \frac{i}{i+j} + \frac{j}{i+j} \cdot \frac{j-1}{i+j-1} \cdot \frac{i}{i+j-2} \cdot f_{i-1,j-2} + \frac{j}{i+j} \cdot \frac{j-1}{i+j-1} \cdot \frac{j-2}{i+j-2} \cdot f_{i,j-3} \]

P4316 绿豆蛙的归宿

\(f_u\) 表示从起点 \(1\) 到 \(u\) 所经过路径的总长度期望。转移方程为

\[f_u = \sum_v \frac{f[v] + w}{d} \]

其中 \(d\) 表示 \(u\) 的度数，存在从 \(u\) 到 \(v\) 的边，\(w\) 表示 \((u,v)\) 的边权

边界：对于起点 \(1\)，\(f[1] = 0\)。

简单在图上 DFS 进行 DP 即可。

P1850 [NOIP 2016 提高组] 换教室

做 2020 年之前的 NOIP 题目总有一种说不上来的年代感，可能那些题真的很特别吧……

让 AI 糊了一个更精致的排版，凑合看吧。

预处理

\(dis(a,b)\) 表示教室 \(a\) 到教室 \(b\) 的最短路径长度，可以在原图上跑一边 Floyd \(O(n^3)\) 预处理得到。

现在问题转化为：在 \(i\) 时刻时，你有 \(k_i\) 的概率把 \(c_i\) 变成 \(d_i\)。

状态定义

\(f_{i,j,0/1}\) 表示前 \(i\) 个时间段，已经提交了 \(j\) 次申请，且第 \(i\) 个时间段 是/否 申请换教室的最小期望体力值。

状态转移

• 第 \(i\) 个时间段不申请（\(j\) 不变）

1. 上一时间段申请

\[f_{i,j,0} = f_{i-1,j,0} + dis(c_{i-1},c_i) \]

2. 上一时间段申请，可能成功或失败，所以要按概率加权，即

\[f_{i,j,0} = f_{i-1,j,1} + dis(d_{i-1},c_i) \cdot k_{i-1} + dis(c_{i-1},c_i) \cdot (1 - k_{i-1}) \]

对于 \(f_{i,j,0}\)，我们取以上两种情况的最小值。

• 第 \(i\) 个时间段申请（\(j\) 要减 \(1\)，即 \(j>0\) 时）

1. 上一时间段不申请，这一时间段申请时，可能成功也可能失败

\[f_{i,j,1} = f_{i-1,j-1,0} + dis(c_{i-1},d_i) \cdot k_i + dis(c_{i-1},c_i) \cdot (1 - k_i) \]

2. 上一时间段申请，此时上一段和这一段都可能成功或失败，需要讨论 \(4\) 种路径组合

\[\begin{aligned} f_{i,j,1} = f_{i-1,j-1,1} &+ dis(c_{i-1},c_i) \cdot (1 - k_{i-1})(1 - k_i) \\ &+ dis(c_{i-1},d_i) \cdot (1 - k_{i-1}) k_i \\ &+ dis(d_{i-1},c_i) \cdot k_{i-1}(1 - k_i) \\ &+ dis(d_{i-1},d_i) \cdot k_{i-1} k_i \end{aligned} \]

对于 \(f_{i,j,1}\)，我们取以上两种情况的最小值。

答案

因为不一定用完所有申请次数，所以答案为

\[\min_{0 \le m \le M, t \in \{0,1\}} f_{n,m,t} \]