学一点整理一点吧... ## 概率dp ### dp求概率 这类题目通常采用顺推，也就是从初始状态推向结果。 [Codeforces 148 D Bag of mice](https://codeforces.com/problemset/problem/148/D) 题目大意：袋子里有 w 只白鼠和 b 只黑鼠，公主和龙轮流从袋子里抓老鼠。谁先抓到白色老鼠谁就赢，如果袋子里没有老鼠了并且没有谁抓到白色老鼠，那么算龙赢。公主每次抓一只老鼠，龙每次抓完一只老鼠之后会有一只老鼠跑出来。每次抓的老鼠和跑出来的老鼠都是随机的。公主先抓。问公主赢的概率。 状态：$f_{i,j}$ 表示当前袋中有 $i$ 只白鼠 $j$ 只黑鼠时,先手获胜概率 起点：$f_{0,j}=0,f_{i,0}=1$ 即没有白鼠时必输，只有白鼠时必赢 终点：$f_{w,b}$ 转移： 1. 公主抓到一只白鼠，公主赢了。概率为 $\frac{i}{i+j}$ 2. 主抓到一只黑鼠，龙抓到一只白鼠，龙赢了。概率为 $\frac{j}{i+j}\cdot \frac{i}{i+j-1}$ 3. 公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只黑鼠，转移到 $f_{i,j-3}$。概率为 $\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{j-2}{i+j-2}$ 4. 公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只白鼠，转移到 $f_{i-1,j-2}$。概率为 $\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{i}{i+j-2}$ 考虑公主赢的概率，第二种情况不参与计算。并且要保证后两种情况合法，所以还要判断 $i$,$j$ 的大小，满足第三种情况至少要有 $3$ 只黑鼠，满足第四种情况要有 $1$ 只白鼠和 $2$ 只黑鼠。 ```c++ double dp[1010][1010]; int w,b; signed main(){ cin>>w>>b; for(int i=1;i<=w;++i) dp[i][0]=1;//只有白鼠 for(int i=1;i<=b;++i) dp[0][i]=0;//没有白鼠 for(int i=1;i<=w;++i){ for(int j=1;j<=b;++j){ dp[i][j]=1.0*i/(i+j); if(j>=3) dp[i][j]+=dp[i][j-3]*j*(j-1)*(j-2)/(i+j)/(i+j-1)/(i+j-2); if(j>=2&&i>=1) dp[i][j]+=dp[i-1][j-2]*j*(j-1)*i/(i+j)/(i+j-1)/(i+j-2); } } printf("%.9lf",dp[w][b]); } ``` [Football](http://poj.org/problem?id=3071) 有 $2^n$ 支球队比赛，每次和相邻球队，两两淘汰，给定任意两支球队相互踢赢的概率，求最后哪只球队最可能夺冠 计算出每个球队获胜的概率，最后找最大值即可 状态：$f_{i,j}$ 在第 $i$ 轮中，第 $j$ 队获胜的概率 起点：$f_{0,j}=1$ 第0轮中每队必然获胜 转移：对于第 $i$ 轮，$j$ 队与 $k$ 队比赛最终 $j$ 胜出的概率为 $f_{i,j}=f_{i-1,j}*f_{i-1,k}*p_{j,k}$ 但如何判断在第 $i$ 轮，$j$ 队与 $k$ 队有可能相遇呢？ 将队从0开始编号并用二进制表示：000，001，010，011，100，101，110，111 可以发现对于任意两个数如果最高的不相同位是第x位，那么将可能在第x轮相遇。例如000与001在第一轮相遇，000与111在第三轮相遇。而判断两队是否在某一轮相遇可以通过 `if ((j >> (i - 1) ^ 1) == (k >> (i - 1)))` 判断 ```c++ double p[130][130], dp[8][130]; signed main() { while (cin >> n) { if (n == -1) return 0; m = 1 << n; for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) cin >> p[i][j]; memset(dp, 0, sizeof dp); for (int i = 0; i < m; ++i) dp[0][i] = 1; for (int i = 1; i <= n; ++i) for (int j = 0; j < m; ++j) for (int k = 0; k < m; ++k) if ((j >> (i - 1) ^ 1) == (k >> (i - 1))) dp[i][j] += dp[i - 1][j] * dp[i - 1][k] * p[j][k]; int ans; double mx = 0; for (int i = 0; i < m; ++i) if (dp[n][i] > mx) { mx = dp[n][i]; ans = i + 1; } cout << ans << endl; } } ``` ### dp求期望 期望小性质： - $E(aX+b)=aE(X)+b$， $a$,$b$是常数 - $E(X+Y)=E(X)+E(Y)$ - $E(XY)=E(X)E(Y)$， $X$,$Y$相互独立 这类题目通常采用逆推，也就是从终止状态到起始状态枚举。 [POJ2096 Collecting Bugs](http://poj.org/problem?id=2096) 一个软件有 s 个子系统，会产生 n 种 bug。某人一天发现一个 bug，这个 bug 属于某种 bug 分类，也属于某个子系统。每个 bug 属于某个子系统的概率是 $\frac{1}{s}$ ，属于某种 bug 分类的概率是 $\frac{1}{n}$。求发现 n 种 bug，且 s 个子系统都找到 bug 的期望天数。 状态：$f_{i,j}$表示已经找到 $i$ 钟bug，$j$ 个子系统的bug，达到目标状态的期望天数 终止： $f_{n,s}=0$ 起始：$f_{0,0}$ 转移： - $f_{i,j}$，发现一个 bug 属于已经发现的 $i$ 种 bug 分类，$j$ 个子系统，概率为 $p_1=\frac{i}{n}\cdot\frac{j}{s}$ - $f_{i,j+1}$，发现一个 bug 属于已经发现的 $i$ 种 bug 分类，不属于已经发现的子系统，概率为 $p_2=\frac{i}{n}\cdot(1-\frac{j}{s})$ - $f_{i+1,j}$，发现一个 bug 不属于已经发现 bug 分类，属于 $j$ 个子系统，概率为 $p_3=(1-\frac{i}{n})\cdot\frac{j}{s}$ - $f_{i+1,j+1}$，发现一个 bug 不属于已经发现 bug 分类，不属于已经发现的子系统，概率为 $p_4=(1-\frac{i}{n})\cdot(1-\frac{j}{s})$ 再根据期望的线性性质，就可以得到状态转移方程： $$ \begin{aligned} f_{i,j} &= p_1\cdot f_{i,j}+p_2\cdot f_{i,j+1}+p_3\cdot f_{i+1,j}+p_4\cdot f_{i+1,j+1} + 1\\ &= \frac{p_2\cdot f_{i,j+1}+p_3\cdot f_{i+1,j}+p_4\cdot f_{i+1,j+1}+1}{1-p_1} \end{aligned} $$ ```c++ signed main() { cin >> n >> s; memset(dp, 0, sizeof dp); for (int i = n; ~i; --i) { for (int j = s; ~j; --j) { if (i == n && j == s) continue; dp[i][j] = (dp[i][j + 1] * i * (s - j) + dp[i + 1][j] * (n - i) * j + dp[i + 1][j + 1] * (n - i) * (s - j) + n * s) / (n * s - i * j); //因为dp[n][s+1],dp[n+1][s],dp[n+1][s+1]都默认为0，不会影响结果，同时也不会导致除0的情况，所以只要跳过dp[n][s]就可以了不必特别处理边界 } } printf("%.4lf", dp[0][0]); } ``` [NOIP2016 换教室](https://uoj.ac/problem/262) 牛牛要上 $n$ 个时间段的课，第 $i$ 个时间段在 $c_i$ 号教室，可以申请换到 $d_i$ 号教室，申请成功的概率为 $p_i$，至多可以申请 $m$ 节课进行交换。第 $i$ 个时间段的课上完后要走到第 $i+1$ 个时间段的教室，给出一张图 $v$ 个教室 $e$ 条路，移动会消耗体力，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，也就是求出最小的期望路程和。 状态：发现转移与已交换课数和上节课是否换课有关，所以可以设为 $f_{i,j,0/1}$ 表示当前第i个时间段以及换了j次这次换/不换(1/0)的路程总和的最小期望 起点：$f_{1,0,0}=f_{1,0,1}=0$，其他为 $inf$ 转移： - 这次不换 $f_{i,j,0}=min(f_{i-1,j,0}+dis_{c_{i-1},c_{i}}\quad,\quad f_{i-1,j,1}+dis_{d_{i-1},c_{i}}\cdot p_{i-1}+dis_{c_{i-1},c_{i}}\cdot (1-p_{i-1}))$ - 这次换 $f_{i,j,1}=min(f_{i-1,j,0}+dis_{c_{i-1},d_{i}}\quad,\quad f_{i-1,j,1}+dis_{d_{i-1},d_{i}}\cdot p_{i-1}+dis_{c_{i-1},d_{i}}\cdot (1-p_{i-1}))$ 其中 $dis_{u,v}$ 用Floyd 求出最短路 ```c++ signed main() {//省略了输入部分 //初始化 for (int i = 1; i <= v; i++) for (int j = 1; j < i; j++) f[i][j] = f[j][i] = 1e9; for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) dp[i][j][0] = dp[i][j][1] = 1e9; //floyd for (int k = 1; k <= v; k++) for (int i = 1; i <= v; i++) for (int j = 1; j < i; j++) if (f[i][k] + f[k][j] < f[i][j]) f[i][j] = f[j][i] = f[i][k] + f[k][j]; dp[1][0][0] = dp[1][1][1] = 0; for (int i = 2; i <= n; i++) for (int j = 0; j <= min(i, m); j++) { dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]], dp[i - 1][j][1] + f[c[i - 1]][c[i]] * (1 - p[i - 1]) + f[d[i - 1]][c[i]] * p[i - 1]); if (j != 0) { dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] + f[c[i - 1]][c[i]] * (1 - p[i]), dp[i - 1][j - 1][1] + f[c[i - 1]][c[i]] * (1 - p[i - 1]) * (1 - p[i]) + f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] + f[d[i - 1]][c[i]] * (1 - p[i]) * p[i - 1] + f[d[i - 1]][d[i]] * p[i - 1] * p[i]); } } double ans = 1e9; for (int i = 0; i <= m; i++) ans = min(dp[n][i][0], min(dp[n][i][1], ans)); printf("%.2lf", ans); } ``` ### 有后效性dp 前置知识：高斯消元 [P3232 [HNOI2013]游走](https://www.luogu.com.cn/problem/P3232) 给定一个 $n$ 个点 $m$ 条边的无向连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。 小 $Z$ 在该图上进行随机游走，初始时小 $Z$ 在 $1$ 号顶点，每一步小 $Z$ 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 $Z$ 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 $m$ 条边进行编号，使得小 $Z$ 获得的总分的期望值最小。 1.考虑经过每条边的期望次数 假设边 $e$ 连接 $u$,$v$ 有：$g_e=\frac{f_u}{d_u}+\frac{f_v}{d_v}$，其中 $f_u$ 表示经过 $u$ 点的期望，$d_u$ 表示 $u$ 点的链接的边数 2.考虑经过每个点的期望次数 $f_u=\sum_{v\in E_u} \frac{f_v}{d_v}$，其中 $E_u$ 表示与 $u$ 相连的点集 其中有2个特殊点： 起点1：刚开始就走过 $f_1=1+\sum \frac{f_v}{d_v}$ 终点n：走到 $n$ 就结束，任何点不能从 $n$ 转移，所以不能将 $\frac{f_n}{d_n}$ 计入答案。故令 $f_n=0$ 将 $f$ 的 $n-1$ 个式子看做 $n-1$ 个 $n-1$ 元方程组，用高斯消元求解 第 $i$ 行：$a_{i,1}*f_1+\ldots+1*f_k+\ldots+a_{k,n-1}*f_{n-1}=0$ ```c++ bool gauss(int n) { for (int i = 1; i <= n; ++i) { int r = i; for (int k = i; k <= n; ++k) if (fabs(a[k][i]) > eps) { r = k; break; } if (r != i) swap(a[r], a[i]); if (fabs(a[i][i]) < eps) return 0; for (int j = n + 1; j >= i; --j) a[i][j] /= a[i][i]; for (int k = i + 1; k <= n; ++k) for (int j = n + 1; j >= i; --j) a[k][j] -= a[k][i] * a[i][j]; } for (int i = n - 1; i; --i) for (int j = i + 1; j <= n; ++j) a[i][n + 1] -= a[i][j] * a[j][n + 1]; return 1; } signed main() { cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> s[i] >> t[i]; mp[s[i]].emplace_back(t[i]); mp[t[i]].emplace_back(s[i]); d[s[i]]++, d[t[i]]++; } for (int i = 1; i < n; ++i) { for (int v: mp[i]) { if (v != n) a[i][v] = -1.0 / d[v]; } a[i][i] = 1; } a[1][n] = 1; gauss(n-1); for (int i = 1; i <= m; ++i) g[i] = a[s[i]][n] / d[s[i]] + a[t[i]][n] / d[t[i]]; sort(g + 1, g + 1 + m); double ans = 0; for (int i = 1; i <= m; ++i) ans += g[i] * (m - i + 1); printf("%.3lf", ans); } ``` [CodeForces 24 D Broken robot](https://codeforces.com/problemset/problem/24/D) 给出一个 $n \times m$ 的矩阵区域，一个机器人初始在第 $x$ 行第 $y$ 列，每一步机器人会等概率地选择停在原地，左移一步，右移一步，下移一步，如果机器人在边界则不会往区域外移动，问机器人到达最后一行的期望步数。 在 $m=1$ 时每次有 $\frac{1}{2}$ 的概率不动，有 $\frac{1}{2}$ 的概率向下移动一格，答案为 $2\cdot (n-x)$。 设 $f_{i,j}$ 为机器人机器人从第 $i$ 行第 $j$ 列出发到达第 $n$ 行的期望步数，最终状态为 $f_{n,j}=0$。 由于机器人会等概率地选择停在原地，左移一步，右移一步，下移一步，考虑 $f_{i,j}$ 的状态转移： - $f_{i,1}=\frac{1}{3}\cdot(f_{i+1,1}+f_{i,2}+f_{i,1})+1$ - $f_{i,j}=\frac{1}{4}\cdot(f_{i,j}+f_{i,j-1}+f_{i,j+1}+f_{i+1,j})+1$ - $f_{i,m}=\frac{1}{3}\cdot(f_{i,m}+f_{i,m-1}+f_{i+1,m})+1$ 在行之间由于只能向下移动，是满足无后效性的。在列之间可以左右移动，在移动过程中可能产生环，不满足无后效性。 将方程变换后可以得到： - $2f_{i,1}-f_{i,2}=3+f_{i+1,1}$ - $3f_{i,j}-f_{i,j-1}-f_{i,j+1}=4+f_{i+1,j}$ - $2f_{i,m}-f_{i,m-1}=3+f_{i+1,m}$ 由于是逆序的递推，所以每一个 $f_{i+1,j}$ 是已知的。 由于有 $m$ 列，所以右边相当于是一个 $m$ 行的列向量，那么左边就是 $m$ 行 $m$ 列的矩阵。使用增广矩阵，就变成了 $m$ 行 $m+1$ 列的矩阵，然后进行高斯消元即可解出答案。 ```c++ void solve(int x) { for (int i = 1; i <= m; i++) { if (i == 1) { a[i][i] = 2; a[i][i + 1] = -1; a[i][m + 1] = 3 + f[i]; continue; } else if (i == m) { a[i][i] = 2; a[i][i - 1] = -1; a[i][m + 1] = 3 + f[i]; continue; } a[i][i] = 3; a[i][i + 1] = -1; a[i][i - 1] = -1; a[i][m + 1] = 4 + f[i]; } for (int i = 1; i < m; i++) { double p = a[i + 1][i] / a[i][i]; a[i + 1][i] = 0; a[i + 1][i + 1] -= a[i][i + 1] * p; a[i + 1][m + 1] -= a[i][m + 1] * p; } f[m] = a[m][m + 1] / a[m][m]; for (int i = m - 1; i >= 1; i--) f[i] = (a[i][m + 1] - f[i + 1] * a[i][i + 1]) / a[i][i]; } int main() { scanf("%d %d", &n, &m); int st, ed; scanf("%d %d", &st, &ed); if (m == 1) { printf("%.10f\n", 2.0 * (n - st)); return 0; } for (int i = n - 1; i >= st; i--) solve(i); printf("%.10f\n", f[ed]); } ```