概率 DP & 有后效性 DP 笔记

一、概率 DP

1. P2473 [SCOI2008] 奖励关

数据范围显然状压，设 $f_{i,s}$ 表示到了第 $i$ 轮吃了集合 $s$ 宝物的期望值。

但是这样是无法转移的，从前往后转移不知道前面的哪些情况是可行的，哪些情况是不可行的；哪些前置状态概率大，哪些前置状态概率小。

于是就可以想到了从后边向前边转移，因为后边的状态一定是在满足前面的限制条件的情况下，等概率选取的，所以可以直接加起来再除以总数求出期望。

if ((s & st[j]) == st[j]) // 后面可以多吃 j
    f[i][s] += max(f[i + 1][s], f[i + 1][s | 1 << j] + p[j]);
else // 后面不能多吃 j
    f[i][s] += f[i + 1][s];
f[i][s] = 1.0 * f[i][s] / n;

二、有后效性 DP

1. P3232 [HNOI2013] 游走

先求出每个点的期望经过次数，易得转移方程：

$$f_i=\{\begin{array}{ll}(\sum f_v)÷{\mathrm{deg}}_i+1& i=1\\ (\sum f_v)÷{\mathrm{deg}}_i& i\in (1,n)\end{array}$$

即 $f_i-\sum (f_v÷{\mathrm{deg}}_i)=[i=1]$，共有 $(n-1)$ 个未知数 $f_i$，$(n-1)$ 个方程，高斯消元即可，时间复杂度 $O(n^3)$。

2. P3750 [六省联考 2017] 分手是祝愿

特殊性质题。

考虑 $k=n$ 时怎么做。容易发现每个按键都不会被若干个按键组合包含，要么是少覆盖了这个按键，要么是多覆盖了更大的按键，而显然不存在一种方案单独消掉更大的按键。所以就是从大到小贪心即可，时间复杂度 $O(n\sqrt{n})$。

有了这个贪心，就很好想到状态 $f_i$ 表示还有 $i$ 个按键要按的时候，想按成还剩 $(i-1)$ 个键的期望次数，有转移：

$$f_i=\frac{i}{n}+\frac{n-i}{n}(f_i+f_{i+1}+1)$$

有 $\frac{i}{n}$ 的概率恰好按到需要被按的 $i$ 个按键，剩下的情况按到了别的按键，必然要按回来，并且还浪费了这一次数。

稍稍化简：

$$f_i=\frac{1}{1-\frac{n-i}{n}}\times \frac{i+(n-i)(f_{i+1}+1)}{n}$$

转移即可。求答案时，如果发现贪心出来的次数都小于 $k$ 次了，直接输出，否则就从贪心的次数一直按到只剩 $k$ 次，再加上 $k$，即 $k+\sum _{i=k+1}^{min}{f}_i$。

3. P5249 [LnOI2019] 加特林轮盘赌

笑点解析：蓝题。

设 $f_{i,j}$ 表示还剩 $i$ 个人时，这 $i$ 个人中的第 $j$ 个要开枪人的存活概率，有 $f_{1,1}=1$，

$$f_{i,j}=\{\begin{array}{ll}{P}_0{f}_{i,i}& j=1\\ P_0{f}_{i-1,j-1}+(1-P_0)f_{i,j-1}& 2<j\le i\end{array}$$

每一个人开完枪之后，所有人都向前移了一位，然后看第一个人死没死分为两种情况（有没有少了一个人）。

考虑用 $f_{1,1}$ 表示出 $f_{i,i}$，就要知道每个 $f_{i-1,j}$ 被计算了多少次，显然 $f_{i-1,j}$ 在计算 $f_{i,j+1+k}$ 时乘了 $1$ 次 $P_0$ 和 $k$ 次 $(1-P_0)$，将 $k=i-j-1$ 代入，令 $A$ 表示所有 $f_{i-1,j}$ 的贡献，则有

$$A=P_0\times \sum _{j=1}^{i-1}(f_{i-1,j-1}\times (1-P_0{)}^{i-j-1})$$

$1-P_0$ 的次幂可以预处理。

则有 $f_{1,1}=(1-P_0)A+(1-P_0{)}^{i-1}{f}_{1,1}$。

移项就能 $n^2$ 算了。