题解 P4550 【收集邮票】

· · 题解

设我们最后买了x张邮票，那么答案就应该是

\begin{matrix}\sum_{i=1}^x i\end{matrix}=\frac{x^2+x}{2}

所以我们需要分别维护x的期望和x^2的期望

我们用f[i]表示买了i种不同的邮票的次数的期望，g[i]表示买了i种不同的邮票的次数的平方的期望

显然，f[0]=g[0]=0

考虑使用f[i]转移f[i+1]

我们有\frac{i}{n}的可能买到一个之前买过的邮票，那么此时次数应该+1，同时我们还有\frac{n-i}{n}的可能买到一个之前没有买过的邮票，那么应该是上一次的次数+1，也就是说，我们可以得到这样的一个等式

f[i+1]=\frac{i}{n}(f[i+1]+1)+\frac{n-i}{n}(f[i]+1)

化简之后可以得到

f[i+1]=\frac{i}{n-i}+f[i]+1

在转移g[i+1]的时候，类比转移f的时候的等式，我们可以得到

g[i+1]=\frac{i}{n}(f[i+1]+1)^2+\frac{n-i}{n}(f[i]+1)^2

利用完全平方公式展开

g[i+1]=\frac{i}{n}(g[i+1]+2f[i+1]+1)+\frac{n-i}{n}(g[i]+2f[i]+1)

化简得

g[i+1]=\frac{2i}{n-i}f[i+1]+\frac{i}{n-i}+g[i]+2f[i]+1

我们从0到n-1进行递推就可以得到最后的答案了

#include <bits/stdc++.h>
using namespace std;
int n;
double f[N],g[N];
int main()
{
    scanf("%d",&n);
    f[0]=g[0]=0;
    for(int i=0;i<n;i++){
        f[i+1]=1.*i/(n-i)+f[i]+1;
        g[i+1]=2.*i/(n-i)*f[i+1]+1.*i/(n-i)+g[i]+2*f[i]+1;
    }
    printf("%.2lf\n",(f[n]+g[n])/2);
    return 0;
}