题目链接https://www.luogu.com.cn/problem/P4550相信应该有不少人我也一样看到概率论题目都马上没有了做下去的欲望了。感觉完全无从下手或者说完全一点也不了解概率论相关知识和结论。但其实只要我们能够知道概率论的各种分布模型知道一些写法套路其实很多概率论题目都是代码写起来非常简短。由洛谷 P4550 这个十分经典的期望 DP 题目知道期望 DP 的一些方法下次也就不会束手无策了。看完题目可以发现其实题目的意思是很简单的收集 n 种邮票但是购买从一块钱开始后续买每次都涨价一元而且买到任何一种邮票的概率都相等。但可能大家都有一种感觉买 n 张邮票连保底机制都没有我怎么知道他什么时候才能买完所有邮票万一他运气不好买无数次都买不到 n 张邮票呢存在这种无限买的特性完全没办法列举出全部状态的期望进行相加似乎就完全无法入手了。但其实利用动态规划 DP的思维方法就可以解决这种情况。而在此之前我们可以先了解一个全期望公式是我们接下来计算期望推导状态转移方程的重要公式。全期望公式可以理解为对于一个状态 X 我付出了代价 w 执行操作 Y 使其有可能达到 $a_1$ , $a_2$ , ... , $a_n$ 这 n 个互斥的状态则状态 X 的期望就是这 n 个状态的概率加权期望和再加上到达每个状态需要付出的代价 w。即概率加权期望和很好理解但是那个操作代价 w 是必须加上的不能遗漏。逻辑上如果没有这个代价 w 也说不通那不就说明从某个状态去到另一个状态居然毫无代价这是不可能的就像人不可能什么都没做凭空从某个地方去到另一个地方一样。知道了这个我们就可以去思考 dp 数组状态的定义了。通常来说我们定义 dp 状态都是“顺推”逻辑的。比如我们要算到达终点的最小代价我们会定义 dp[i] 是从起点走了 i 步的最小代价。但如果放到此时计算这种期望的上也这样定义就发现不对了。按照刚刚的思路我们应该定义 dp[i] 是买了 i 张邮票的花钱的期望。但我们能很快发现我们还是绕回了刚刚的问题我们无法知道要买几次才能买完所有这 i 张邮票他运气好可以买 i 次也可以运气烂到不行买无数次我们完全无法计算每一个 dp[i] 的数值。所以说在期望 dp 中我们普遍采用“倒推”的定义方法。即定义一个 g[i] 为手上已经有了 i 张邮票买到 n 张邮票时候所花费的钱的期望。由此我们再看看如何进行推导就能理解为什么“倒推”定义能解决我们一直困扰的买“无数次”的问题了。当前手上有了 i 张邮票那么下一刻我们当然是继续买邮票了。而如果我们买了下一张票我们就可能达到两种互斥的状态即买到一张没买到过邮票或者买到一张买到过的邮票。这很好理解我们能发现的是如果买到一张之前买到过的邮票那么这个状态就又是 g[i] 了和没买一样唯一不同的是邮票价格变动了。如果当前是第 k 次买邮票了我就记为 $g[i]_k$ 。那么买完一张新邮票的状态就能达到状态 $g[i]_{k1}$ 和 $g[i1]_{k1}$ 。那么还有个重要问题就是我们当然想利用刚刚的全期望公式来推导转移方程那我们就要知道从 $g[i]_k$ 到 $g[i]_{k1}$ 或者 $g[i1]_{k1}$ 的代价 w是什么。我们可以先来看看从 $g[i]_k$ 到 $g[i]_{k1}$ 是到底付出了什么代价。可以发现因为买了一次邮票无论有没有买到一张新邮票我们后续买的邮票价格都是直接加了一元。而后续我们需要买几次邮票呢我们似乎还不知道但我们依旧可以计算一下这个期望。我们需要再定义一个 f[i] 为手上已经有了 i 张邮票买到 n 张邮票时候还要买几次的期望。那我们现在可以发现无论是 $g[i]_k$ 还是 $g[i]_{k1}$ 买到 n 张邮票的次数期望其实都是 f[i] 。从 $g[i]_k$ 到 $g[i]_{k1}$ 影响了后面期望买 f[i] 次的价格都升价了一元所以从 $g[i]_k$ 到 $g[i]_{k1}$ 的代价也就是 f[i] 因为总共升价了 f[i] 元。但是不能忘记的是我们只是计算了后续买 f[i] 次的价格而在 $g[i]_k$ 和 $g[i]_{k1}$ 这两个状态买一张票的价格也是不一样的一个是 k 元一个是 k1 元。当前票价了发生了一元的改变我们也需要加上。最终得到从 $g[i]_k$ 到 $g[i]_{k1}$ 的代价其实就是 f[i]1包括了未来票价和当下票价的变动。那其实对于从 $g[i]_k$ 到 $g[i1]_{k1}$ 也是同理。状态转移后当前票价从 k 元上涨到 k1 元而且也导致了未来我还期望买 f[i1] 次的票价都上涨了一元即从 $g[i]_k$ 到 $g[i1]_{k1}$ 的总代价应该是 f[i1]1。即如图所示的状态转移接下来的问题就很简单了当前手上有 i 张邮票总共有 n 种邮票那么我买到一张之前买到过的邮票概率就是买到一张没买过的邮票的概率当然就是。那么根据全期望公式我们就可以得到看着有点复杂而且式子右边还有 g[i] 存在不利于我们进行 dp 计算所以还需要化简一下把 g[i] 全部放到左边就可以得到这就得到了我们所需要的状态转移公式了。而我们也发现我不仅解决了我们刚刚无法解决的“无限买”的问题而且在这个状态定义里g[0] 其实就是答案而且 g[n] 很显然当然是 0 了直接一个线性的 dp 即可解决问题。而且也可以发现这个做法似乎有点像高中时期很多人都可能接触过的马尔科夫链。可以看到他们都是从一个状态转移到另一个状态的时候有可能会直接自环回到自身这也是我们刚刚被困扰的“无限买”的问题。当然我们问题还没完全解决刚刚定义的 f[i] 次数期望还没计算好。但实际上这个道理和刚刚的 g[i] 几乎可以说完全一样甚至还更加简单。在 $f[i]_k$ 状态转移无论是转移到 $f[i]_{k1}$ 还是 $f[i1]_{k1}$ 都只有票价本身发生变动代价都为 1 。则按照刚刚那样推导可以得到经过化简可以得到同样很明显可以发现 f[n] 也是 0 都有 n 张邮票了已经买完了当然不需要再买下去了。虽说刚刚的解释了这么多但实际上代码也就写了这两个状态转移方程上去直接 for 循环线性 dp 就结束了代码十分简洁没有难度状态转移方程的推导也不难但是如果事先不知道这么做也很容易被“无限买”的问题绕进去。#include bits/stdc.h using namespace std; //记得用double即可 double f[10005]; double g[10005]; void solve(){ int n; cinn; f[n]g[n]0; for(int in-1;i0;--i){ f[i]f[i1](double)n/(double)(n-i); } for(int in-1;i0;--i){ g[i]g[i1]f[i1](double)i/(double)(n-i)*f[i](double)n/(double)(n-i); } coutfixedsetprecision(2)g[0]\n; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int t1; //cint; while(t--) solve(); return 0; }