题解 P4550 【收集邮票】

Update:2020.2.1 发出题解的第二天

初学期望DP，有问题请指出

• 定义状态

众所周知，期望DP的定义状态一般都为已经……还需要……的期望

由于本题需要求的就是

自己得到所有种类的邮票需要花费的钱数目的期望。

那么我们就可以定义一个 ans ，它的意义是：

但是题目中有一个条件 *皮皮购买第k张邮票需要支付k元钱* 这意味着购买价格是与购买次数有关的。 所以我们还需要定义一个状态 $num$ ，它的意义是： $num(i)$：已经收集到了 $i$ 种邮票，还需要购买的次数的期望。 * 初始化：$num(n)=0$，$ans(n)=0

这个应该不需要我讲吧qwq

• 状态转移

首先吧这个写在前面

期望公式：E(X)=\sum p_{i}\cdot x_{i} ，其中 p_i 是事件 i 发生的概率，x_i 是权值。

发现 num 的转移是比较简单的，先考虑 num。有以下两种情况：

• 买到之前买到过的邮票种类，此时 x=num(i)+1（种类总数不变），p=\dfrac {i}{n}

• 买到之前没有买到过的，此时 x=num(i+1)+1（总种类数量+1），p=\dfrac {n-i}{n}

注：以上的 x 指的是次数。

根据公式，我们就可以得到关于 num 的公式：

num(i)=(num(i)+1)\times\dfrac {i}{n}+(num(i+1)+1)\times\dfrac {n-i}{n}

化简之后得到状态转移方程：

num(i)=\dfrac{num(i+1)\times\dfrac {n-i}{n}+1}{1-\dfrac {i}{n}}

得到 num 后，我们再思考 ans 的转移，同样是以上的两种情况

• 买到之前买到过的邮票种类：此时 x=ans(i)+num(i)+1（种类+1，总花费=之前花费+本次花费），p=\dfrac {i}{n}

• 买到之前没有买到过的，此时 x=ans(i+1)+num(i+1)+1（同上），p=\dfrac {n-i}{n}

然后我们又轻松地得到了关于 ans 的公式：

ans(i)=(ans(i)+num(i)+1)\times\dfrac {i}{n}+(ans(i+1)+num(i+1)+1)\times\dfrac {n-i}{n}

请自行化简

既然我们有了转移方程，那就开写呗

num[n] = 0; ans[n] = 0;
for(int i = n - 1; i >= 0; i--)
{
    double p1 = frac(i, n), p2 = frac(n - i, n);
    num[i] = (p2 * num[i + 1] + 1) / (1 - p1);
    ans[i] = (ans[i + 1] * p2 + num[i] * p1 + num[i + 1] * p2 + 1) / (1 - p1);
}
cout << fixed << setprecision(2) << ans[0];

注：以上的 frac(x,y) 表示 \dfrac{x}{y}

以上就是中心代码

但是这篇题解并没有完，题解中的几个细节还没有完善别急着抄代码啊

• Q：为什么要在次数和价格的计算过程中 +1

A：在天数的过程中， num(i) 和 num(i+1) 其实计算的是前一次购买的期望次数，如果要转化为这一次，还需要在次数上 +1 才可以。同样地，ans(i)+num(i+1) 与 ans(i+1)+num(i+1) 这两个价格也只是前一次购买的总价格，而每次购买，邮票的价值都会根据次数的增长将价格 +1，所以最终计算，还需要 +1 才可以。

• Q：为什么要倒序循环

A：正序循环也是可以的，只需要将状态“已经……还需要……的期望”改成“……需要……的期望”即可，大家不妨去推导试试。

end.