题解 P4550 【收集邮票】

转载自vercont的洛谷日报 如有兴趣学习更多期望知识，请点击[这里](https://45475.blog.luogu.org/mathematical-expectation) # 题目链接： 但这应该是个经典问题吧 和上面一道UVA题目有一点点像 行了不废话了放链接 https://www.luogu.org/problem/P4550 - 题意简叙： n个数1~n，第k次取数需要k元，每次取数对于所有数概率均等（$\frac{1}{n}$）,问取完n个数的期望花费 --- ### 分析： **这个题意千万别理解错了，不是买到k需要k元，而是第k次买需要k元。可能是题面就模糊，但是结合一下样例和难度颜色应该也能看出来** 这道题是那题的升级版，要用到高次的期望，但输出不用那么麻烦了。 首先第一步很好转化吧，设用了x步，则花费为 $$\sum_{i=1}^{x}i=\frac{(x^2+x)}{2}$$ 现在就转换成要求上式的期望。 有了前面那题的基础现在考虑起来就简单了 维护一个线性期望$a$，平方期望$f$（都是数组） 好吧再清楚地表达一下： $a[i]$表示找完i个数之后还需要的次数的期望 $f[i]$表示找完i个数之后还需要的**次数平方**的期望 不难想到最后的答案是$\frac{a[0]+f[0]}{2}$ 下面就开始考虑状态转移（dp？） ---- ### 先来考虑$a[i]$ $$a[i]=?$$ #### 情况1，买到买过的 买过的是i个，概率为$\frac{i}{n}$,花费就相当于记在买到i时候的账上了（从i账上查），得到花费为$a[i]+1$ 可得到式子$\frac{i}{n}(a[i]+1)$ #### 情况2，买到没买过的 没买过的是$n-i$个，概率为$\frac{n-i}{n}$,花费就相当于记在买到i+1时候的 账上了（从i+1账上查），因为当前多买了一个，得到花费为$a[i+1]+1$ 可得到式子$\frac{n-i}{n}(a[i+1]+1)$ 两种情况一合并，得： $$a[i]=\frac{i}{n}(a[i]+1)+\frac{n-i}{n}(a[i+1]+1)$$ 这时就发现了，推着推着出现了i+1，自然而然的想到了倒推 边界$a[n]=0$~~都得全了还买什么~~ 但是这个式子固然能做，是不是麻烦了点？ 那么把它化简看看能出来什么... ……&%&（）……&……&*%……&*%……*&% 一顿猛算后发现： $$a[i]=a[i+1]+\frac{n}{n-i}$$ 当然如果熟练了，直接心算都没毛病啦~~ --- ### 然后考虑$f[i]$ 唉有了前面osu的铺垫这还不是轻而易举？ 跟推a的时候一个思路，新的或旧的，唯一就把平方拆开就行喽 $$f[i]=\frac{i}{n}(f[i]+2\times a[i]+1)+\frac{n-i}{n}(f[i+1]+2\times a[i+1]+1)$$ - 倒推 - 边界$f[n]=0$ - 可算，但麻烦 - 化简 OK既然上面讲了写式子下面就说说化简的事吧~ $$f[i]=\frac{i}{n}(f[i]+2\times a[i]+1)+\frac{n-i}{n}(f[i+1]+2\times a[i+1]+1)$$ 把第一个括号拆成$f[i]$和$2\times a[i]+1$两部分 然后把$\frac{i}{n}\times f[i]$给移到左边，合并得： $$\frac{n-i}{n}f[i]=\frac{i}{n}(2\times a[i]+1)+\frac{n-i}{n}(f[i+1]+2\times a[i+1]+1)$$ 然后两边同除$\frac{n-i}{n}$ $$f[i]=\frac{i}{n-i}(2\times a[i]+1)+f[i+1]+2\times a[i+1]+1$$ 就简单一些了。 代码中精度转换注意一下，不要丢失 end ### code： ```cpp #include<cstdio> using namespace std; double a[10005],f[10005]; int main() { int n; scanf("%d",&n); a[n]=0; f[n]=0; for(int i=n-1;i>=0;i--) { a[i]=a[i+1]+1.0*n/(n-i); f[i]=1.0*i/(n-i)*(2*a[i]+1)+f[i+1]+2*a[i+1]+1; } printf("%.2lf\n",(f[0]+a[0])/2); return 0; } ```