本文由 发布，转载请注明出处，如有问题请联系我们！ 发布时间: 2021-07-24【算法学习笔记】概率与期望DP
加载中文中学习培训自 Sengxian 师兄的blog
以前也在CF上写了一些几率DP的题并做了汇总
提议阅读文章完文中再去然后阅读文章本文：Here
序言
单纯性仅用到几率的题并并不是许多，从目前的 OI/ACM 赛事中看来，大部分题型必须 几率与期待融合起來（期待便是用几率界定的），因此文中关键叙述期待 DP。
期待 DP 有一些固定不动的方式，这儿分多种多样方式来叙述。
解读
例一
#3036. 绿豆蛙的归处
句意：
给出一个起始点为 \(1\)，终点站为 \(n\) 的有向无环图。抵达每一个端点时，如果有 \(K\) 条离去该点的路面，能够 挑选随意一条路面离去该点，而且迈向每一条路的几率为 \(\frac 1 K\)。询问你从 \(1\) 考虑来到 \(n\) 的途径期待总长多少钱。
方式一：立即界定期待情况
这题的终点站很确立，那便是来到 \(n\) 即终止。针对期待 DP，大家一般选用反序的方法来界定情况，即考虑到从当今情况抵达终点站的期待成本。由于在大部分状况下，终点站不唯一，而起始点是唯一的。
大家界定 \(dp(i)\)为从 \(i\) 考虑来到终点站 \(n\) 的途径期待总长，依据全期望公式，获得（设 \(G_i\)为从 \(i\) 的边的结合）：
由于这是一个有向无环图，每一个点必须 其能抵达的点的情况，故大家选用拓扑结构序的反序开展测算就可以。
【AC Code】
const int N = 100000, M = 2 * N;
int n, m;
struct node { int v, w;};
vector<node>e[N];
int d[N]; // 出度
double f[N]; // dp
double dfs(int u) {
if (f[u] >= 0)return f[u];
f[u] = 0;
for (auto [v, w] : e[u]) { // tuple 需打开 C 17
f[u] = (w dfs(v)) / d[u];
}
return f[u];
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
memset(f, -1, sizeof(f));
cin >> n >> m;
for (int i = 0; i < m; i) {
int u, v, w;
cin >> u >> v >> w;
e[u].push_back(node{v, w});
d[u] ;//出度
}
cout << fixed << setprecision(2) << dfs(1);
}
方式二：运用期待的线形特性
依据期待的线形特性，\(E[aX bY]=aE[X] bE[Y]\)。因此此外一种求期待的方法是各自算出每一种成本造成的期待奉献，随后求和获得回答。在题中中，途径期待总长相当于一条边造成的期待奉献之和。而一条边造成又相当于历经这条边的期待频次乘这条边的成本。因此，大家只必须 算每条边的期待历经频次就可以。
边 \((u,v,w)\) 的期待历经频次是不太好立即算的，但如果我们能算得点 \(u\) 的期待历经频次为 \(dp(u,v)\)，那麼边 \((u,v,w)\) 的期待历经频次是 \(dp(u)*\frac1{|G_u|}\) ，对答案的奉献便是 \(w*dp(u)*\frac1{|G_u|}\)
如何计算点 \(u\) 的期待历经频次 \(dp(u)\)呢？大家仍然考虑到 DP 的方法，最先有 \(dp(u) = 1\)，迁移采用刷表的方法：
在使用 边 \(e\) 刷表的与此同时，边 \(e\) 的奉献就可以测算了，十分简约。由于这类方式测算回答十分的方便快捷，并且应用领域广，因此这类『运用期待的线形特性，独立测算奉献的方式』是大家测算期待优选的方式。
【AC Code】这儿贴 Sengxian 师兄的编码
typedef long long ll;
inline int readInt() {
static int n, ch;
n = 0, ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) n = n * 10 ch - '0', ch = getchar();
return n;
}
const int MAX_N = 100000 3, MAX_M = MAX_N * 2;
struct edge {
edge *next;
int to, cost;
edge(edge *next = NULL, int to = 0, int cost = 0): next(next), to(to), cost(cost) {}
} pool[MAX_M], *pit = pool, *first[MAX_N];
int n, m, deg[MAX_N], outDeg[MAX_N];
double f[MAX_N];
void solve() {
static int q[MAX_N];
int l = 0, r = 0;
q[r ] = 0;
double ans = 0;
f[0] = 1.0;
while (r - l >= 1) {
int u = q[l ];
for (edge *e = first[u]; e; e = e->next) {
f[e->to] = f[u] / outDeg[u];
ans = f[u] * e->cost / outDeg[u];
if (--deg[e->to] == 0) q[r ] = e->to;
}
}
printf("%.2f\n", ans);
}
int main() {
n = readInt(), m = readInt();
for (int i = 0, u, v, w; i < m; i) {
u = readInt() - 1, v = readInt() - 1, w = readInt();
first[u] = new (pit ) edge(first[u], v, w);
deg[v] , outDeg[u] ;
}
solve();
}
例二
然后大家考虑到 Codeforces 518D 这题，便于感受方式二的益处。
句意：有 \(n\) 本人排成一列，每秒钟中团队最前边的人有 \(p\) 的几率踏入电梯轿厢（一旦踏入就不容易下电梯轿厢），或是有 \(1-p\) 的几率没动。询问你 \(T\) 秒之后，在电梯轿厢上的人的期待。
方式一
在题中那样一个状况中，方式一是用不上的，由于大家的完毕情况不确立。
方式三：应用期待的界定测算
假如 \(X\) 是离散变量的随机变量，輸出数值 \(x_1,x_2,...\)，輸出值相对应的几率为 \(p_1,p_2,...\)，那麼期待值是一个无尽数列的和（如果不收敛性，那麼期待不会有）：
在题中中，假如设 \(dp(i,j)\) 为 \(i\) 秒之后，电梯轿厢上面有 \(j\) 本人的几率，那麼回答是：
因此大家只需规定 \(dp(i, j)\) 就可以了，初值 \(dp(0, 0) = 1\) 就可以了，依然是选用刷表法：
【AC Code】
const int N = 2e3 10;
double p, dp[N][N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, t;
cin >> n >> p >> t;
dp[0][0] = 1;
for (int i = 0; i < t; i) {
dp[i 1][n] = dp[i][n];
for (int j = 0; j < n; j) if (dp[i][j] > 1e-10) {
dp[i 1][j 1] = dp[i][j] * p;
dp[i 1][j] = dp[i][j] * (1 - p);
}
}
double ans = 0;
for (int i = 0; i <= n; i) ans = i * dp[t][i];
cout << fixed << setprecision(6) << ans;
}
方式二
那麼以前提及的应用领域广的方式二，是不是能在这儿用呢？回答是毫无疑问的。
持续方式三的 DP，大家何不将情况中间的迁移抽象性成边，只不过是仅有 \(dp(i, j)\) 到 \(dp(i 1, j 1)\) 的边才有所为 \(1\) 的边权，其他都为 \(0\)。由于这一 DP 包含了全部很有可能发生的状况，因此大家依然能够 运用期待的线形特性，在刷表的全过程中开展测算回答。
题中中，沒有形象化的边的定义，可是我们可以将情况中间的迁移抽象性成边，因为 \(dp(i, j)\)到 \(dp(i 1, j 1)\) 这一个迁移是对答案有 \(1\) 的奉献的，因此大家将他们中间的边权赋为 \(1\)。
这一题将方式二抽象概念了，事实上大部分题并不是是形象化的，只是这类抽象性的方式。
const int N = 2e3 10;
double p, dp[N][N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, t;
cin >> n >> p >> t;
dp[0][0] = 1;
double ans = 0;
for (int i = 0; i < t; i) {
dp[i 1][n] = dp[i][n];
for (int j = 0; j < n; j) if (dp[i][j] > 1e-10) {
dp[i 1][j 1] = dp[i][j] * p;
dp[i 1][j] = dp[i][j] * (1 - p);
ans = dp[i][j] * p;
}
}
cout << fixed << setprecision(6) << ans;
}
例三
BZOJ 3450
句意：给出一个编码序列，一些部位不确定（是 \(\texttt{o}\) 与 \(\texttt{x}\) 的概率各占 \(\P%\)）。针对一个 \(\texttt{ox}\) 编码序列，持续 \(x\) 长短的 \(\texttt{o}\) 会获得 \(x^2\) 的盈利，我想问一下最后获得的编码序列的期待盈利多少钱？
剖析
这一题假如一段一段的解决，事实上并并不是非常好做。大家观查到 \((x 1) ^ 2 - x ^ 2 = 2x 1\)，那麼依据期待的线形特性，我们可以独立算每一个字符的奉献。大家设 \(dp_i\) 为考虑到前 ii 字符的期待评分，\(l_i\) 为以 \(i\) 为末尾的 comb 的期待长短，\(Comb_i\) 为第 \(i\)字符，那麼有 3 种状况：
- \(s_i = o\) ，则 \(dp_i = dp_{i - 1} l_{i - 1} * 2 1,l_i = l_{i - 1} 1\)
- \(s_i = x\) ，则 \(dp_i = dp_{i - 1}\)
- \(s_i =\ ?\)， 则 \(dP_i = dp_{i - 1} \frac{l_i*2 1}{2},l_i = \frac{l_{i - 1} 1}{2}\)
针对前二种状况，实际上 是十分形象化的，针对第三种状况，事实上是求了一个总长度。比如 ?oo，二种状况的长短 \(l_i\) 各自为 \([0,1,2]\) 和 \([1,2,3]\) ，可是求了均值以后，长短 \(l_i\) 变成了 \([0.5,1.5,2.5]\) ，那样因为大家的奉献是一个有关长短的一次代数式 \((2x 1)\) ，因此长短均值以后，奉献也等同于求了一个均值，当然可以求取恰当的评分期待。
【AC Code】
const int N = 3e5 10;
double dp[N], Comb[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n; string s;
cin >> n >> s;
for (int i = 0; i < n; i) {
if (s[i] == 'o') {
dp[i] = dp[i - 1] Comb[i - 1] * 2 1;
Comb[i] = Comb[i - 1] 1;
} else if (s[i] == 'x') {
dp[i] = dp[i - 1];
Comb[i] = 0;
} else {
dp[i] = dp[i - 1] (Comb[i - 1] * 2 1) / 2;
Comb[i] = (Comb[i - 1] 1) / 2;
}
}
cout << setprecision(4) << fixed << dp[n - 1];
}
思索：假如长短为 \(a\) 的 comb 的奉献为 \(a^3\) 时该如何解决？
Tips：因为 \((a 1)^3 - a^3 = 3a^3 3a 1\) ，因此我们要维护保养 \(a^2\) 和 \(a\) 的期待，留意 \(E_{a^2} \not= E^2_a\)，因此维护保养 \(a^2\) 的期待是必需的。
例四
BZOJ 4318
句意：给出一个编码序列，每一个部位 \(o\) 的概率为 \(p_i\) ，为 \(x\) 的概率为 \(1-p_i\) 。针对一个 \(\texttt{ox}\) 编码序列，持续 \(x\) 长短的 \(\texttt{o}\) 会获得 \(x^3\) 的盈利，我想问一下最后获得的 \(ox\) 编码序列的期待盈利多少钱？
剖析
持续例三的构思，大家或是各自求每一个部位的奉献。依据 \((a 1)^3 - a^3 = 3a^3 3a 1\)，大家只必须 维护保养 \(l(i)\)为以 \(i\) 为末尾的 comb 的期待长短，\(l_2(i)\)为以 \(i\) 为末尾的 comb 的期待长短的平方米。留意 \(E[a^2] \not =E^2[a]\)，因此维护保养 \(a^2\) 的期待是必需的。
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
double p, l1 = 0, l2 = 0, ans = 0;
cin >> n;
for (int i = 0; i < n; i) {
cin >> p;
ans = (3 * l2 3 * l1 1) * p;
l2 = (l2 2 * l1 1) * p;
l1 = (l1 1) * p;
}
cout << fixed << setprecision(1) << ans;
}
汇总
期待 DP 一般来说有它固定不动的方式，一种方式是立即 DP，界定情况为到终点站期待，选用反序测算获得回答。一种方式是运用期待的线形特性，对奉献各自测算，这类方式一般规定大家求出每一种成本的期待应用频次，而每一种成本通常反映在 DP 的迁移当中。最终的2个练习题是典型性的分离出来自变量，用期待的线形特性测算回答的事例，假如情况过度极大，那麼就得考虑到分离出来随机变量了。
本汇总仅仅表述了几率与期待 DP 的冰山一角，它能够 变幻无常，但这些事实上并不只归属于几率与期待 DP，真真正正关键的內容，或是逃不了大家几类方式。
要想深入了解一些几率的DP的请阅读文章本文：Here
The desire of his soul is the prophecy of his fate
你生命的冲动，就是你运势的先知。
