BZOJ 1426 - 收集邮票 | Sengxian's Blog

BZOJ 1426 - 收集邮票

#数学 #动态规划 #概率与期望动态规划 #概率与期望

Published on 2016-11-28

描述

有 $n(n\le 10000)$ 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 $n$ 种邮票中的哪一种是等概率的，概率均为 $\frac 1 n$ 。但是由于凡凡也很喜欢邮票，所以皮皮购买第 $k$ 张邮票需要支付 $k$ 元钱。现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

分析

设 $g_i$ 为已经拥有了 $i$ 种，买到 $n$ 种的期望次数，那么有：

g_i = \frac i n \cdot g_i + \frac {n - i} n \cdot g_{i + 1}

化简得到 $g_i = g_{i + 1} + \frac \cdot n {n - i}$ 且 $g_n = 0$ 。

我们设 $f_{i, j}$ 为已经拥有了 $i$ 种，已经买了 $j$ 张，买到 $n$ 种的期望花费，那么有：

f_{i, j} = \frac i n \cdot f_{i, j + 1} + \frac {n - i} n \cdot f_{i + 1, j + 1} + (j + 1)

这个是没办法算的，因为 $j$ 是可以无限增长的，我们考虑干掉第二维是 $j + 1$ 的项，这需要一些恒等式来帮助我们。考虑回到期望最原始的定义上，设 $P(i, j)$ 为已经拥有了 $i$ 种，买 $j$ 次能买到 $n$ 种的概率，则：

g_i = \sum_{k = 0}^{\infty}k\cdot P(i, k)

考虑 $f_{i, j}$ ：

考虑 $f_{i, j + 1} - f_{i, j}$ ：

f_{i, j + 1} - f_{i, j} = \sum_{k = 0}^{\infty} k \cdot P(i, k) = g_i

这就说明， $f_{i, j + 1} = f_{i, j} + g_i$ ，我们用这个等式稍微化一下 $f_{i, j}$ 的递推式：

f_{i, j} = \frac i n \cdot (f_{i, j} + g_i) + \frac {n - i} n \cdot (f_{i + 1, j} + g_{i + 1}) + (j + 1)

根据这个递推式， $f_{i, j}$ 只需要 $f_{i + 1, j}$ 的值，由于我们只需要知道 $f_{0, 0}$ 的答案，我们只对 $j = 0$ 做递推，设 $F_i = f_{i, 0}$ ，那么将上式整理可得：

F_i = \frac {i \cdot g_i + (n - i)(F_{i + 1} + g_{i + 1}) + n} {n - i}

这就是一个标准的递推式了，复杂度： $O(n)$ 。

代码

//  Created by Sengxian on 2016/11/28.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1426 期望 DP
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 10000 + 3;
double f[MAX_N], g[MAX_N];

int main() {
    int n;
    cin >> n;

    g[n] = 0, f[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        g[i] = g[i + 1] + (double)n / (n - i);
        f[i] = (i * g[i] + (n - i) * (f[i + 1] + g[i + 1]) + n) / (n - i);
    }

    printf("%.2f\n", f[0]);
    return 0;
}

概率与期望 DP 总结 BZOJ 3566 - [SHOI2014]概率充电器