P4550 收集邮票 神仙题

概率神仙题，期望也可以提前计算费用。

链接

设 (f_i) 表示已经有 (i) 张，期望再拿多少次拿到 (n) 张。

那么显然，有：

[f_{i}=f_{i+1}+frac{n}{n-i} ]

这个比较简单。

设 (g_i) 表示已经有 (i) 张，期望再花多少钱才能拿到 (n) 张。注意，这里我们假设之前的拿取次数为 (0) ，也就是说交钱从 (1) 开始交。

我们先给出 (g) 的计算公式，然后再进行讲解：

[g_{i}=frac{i}{n}(g_i+f_i+1)+frac{n-i}n (g_{i+1}+f_{i+1}+1) ]

我们有 (frac i n) 的概率拿到我们已经拿到的一张，因为 (g) 的定义是从 (1) 开始付钱，所以当我们再拿了一张时之前所有付的钱都要加一。而我们期望付了 (f_i) 次的钱，所以有左式。加号右边同理。

于是这个题就可以做了。

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 10010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n;
dd f[N],g[N];

int main(){
    read(n);
    f[n]=0;
    for(int i=n-1;i>=0;i--) f[i]=f[i+1]+(dd)n/(dd)(n-i);
    for(int i=n-1;i>=0;i--) g[i]=(dd)i/(dd)(n-i)*(f[i]+1)+g[i+1]+f[i+1]+1;
    printf("%0.2lf
",g[0]);
}