11 期望DP：收集邮票

11期望DP

收集邮票

题目描述

有 $n$ 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 $n$ 种邮票中的哪一种是等概率的，概率均为 $1/n$。但是由于凡凡也很喜欢邮票，所以皮皮购买第 $k$ 次邮票需要支付 $k$ 元钱。

现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

输入格式

一行，一个数字 $N$（$N \le 10000$）。

输出格式

输出要付出多少钱，保留二位小数。

样例 #1

样例输入 #1

3

样例输出 #1

21.25

• 定义状态

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

由于本题需要求的就是

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

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

$ex(i)$：已经收集到了 i 种邮票，还需要花费的钱数的期望。

但是题目中有一个条件

皮皮购买第k张邮票需要支付k元钱

这意味着购买价格是与购买次数有关的。

所以我们还需要定义一个状态 num ，它的意义是：$num(i)$：

已经收集到了 i 种邮票，还需要购买的次数的期望。

• 初始化：$num(n)=0$，$ex(n)=0$

这个应该不需要我讲吧qwq

• 状态转移

首先吧这个写在前面

期望公式：$E(X)= \sum pi​⋅xi$​ ，其中 pi​ 是事件 i 发生的概率，xi​ 是权值。

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

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

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

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

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

$num(i)=(num(i)+1)×\frac{i}{n}+(num(i+1)+1)×\frac{n-i}{n}$

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

$$num(i)= \frac{num(i+1)×\frac{n-i}{n}+1}{1−\frac{n-i}{n}}​$$

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

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

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

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

$ex(i)=(ex(i)+num(i)+1)×\frac{i}{n}​+(ex(i+1)+num(i+1)+1)×​\frac{n-i}{n}$

请自行化简

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

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

double num[10005]={0},ex[10005]={0};
signed main()
{
    int n;
    cin>>n;
    num[n]=0;ex[n]=0;

    for(int i=n-1;i>=0;i--)
    {
        double p=(double)n/(n-i);
        num[i]=p+num[i+1];
        ex[i]=p*num[i]+ex[i+1];
    }
    // for(int i=0;i<=n;i++)cout<<num[i]<<" ";
    // cout<<endl;
    // for(int i=0;i<=n;i++)cout<<ex[i]<<" ";
    // cout<<endl;
    printf("%.2lf",ex[0]);
    //cout<<ex[0]<<"\n";
    return 0;
}