收集邮票

也许更好的阅读体验
$Description$Description

有 $n$n种邮票，每天等概率的买一张邮票，第 $i$i天购买要花费 $i$i元，求收集 $n$n种邮票的期望花费

$Solution$Solution

先设 $f\left[i\right]$f[i]表示买到 $i$i种邮票后，离买到 $n$n种邮票的期望还差天数
和最上面那题一样的处理方法
考虑当前买了 $i$i张邮票，再买一张邮票，有两种情况

1. 有 $\frac{i}{n}$ni​的概率买到重复的邮票，此时仍只买到 $i$i张邮票
2. 有 $\frac{n-i}{n}$nn−i​的概率买到没买过的邮票，此后就已买到 $i+1$i+1张邮票

需要注意的是，无论哪种情况，都过了一天
所以有
$f\left[i\right]=\frac{i}{n}f\left[i\right]+\frac{n-i}{n}f[i+1]+1$f[i]=ni​f[i]+nn−i​f[i+1]+1
将其化简
$f\left[i\right]=f[i+1]+\frac{n}{n-i}$f[i]=f[i+1]+n−in​

初值 $f\left[n\right]=0$f[n]=0，答案为 $f\left[0\right]$f[0]
应逆向循环

当然这只是期望天数，不是期望花费
设 $g\left[i\right]$g[i]表示 拥有(不是买) $i$i种邮票， 买到 $n$n种邮票的期望花费
考虑当前拥有了 $i$i张邮票，买一张邮票，有两种情况

1. 有 $\frac{i}{n}$ni​的概率买到重复的邮票，此时仍只拥有 $i$i种
2. 有 $\frac{n-i}{n}$nn−i​的概率买到没买过的邮票，此后就已拥有 $i+1$i+1张邮票

需要注意的是，无论哪种情况，都买了一张邮票
此时我们不知道每张邮票多少钱
但我们知道每张邮票和过了多少天有关
这次的注意写在前面，我们是认为有了 $i$i张邮票后才开始，所以第一天邮票价格为 $1$1元
为什么这么设？
我们不知道也不好处理出前面买了多少张邮票，再买到一张邮票要多少钱
但是我们知道第一天肯定是只要 $1$1元的，答案为 $g\left[0\right]$g[0]，中间的过程不重要，只需推出最终答案
我们借助初始状态的这条非常有用的性质于是就设出了这样的 $g$g
这样我们可以知道

1. 若买到重复的邮票，我们知道，因为是设当前是第一天，所以原本希望买到的邮票的天数又往后推了一天，所以总价格要多 $f\left[i\right]$f[i]元，还要加上自己的 $1$1元
2. 若买到没买过的邮票，同理，因为后面的 $g[i+1]$g[i+1]也是从第 $1$1天开始考虑的，所以原本希望买到的邮票数也往后推了一天，所以价格要多 $f[i+1]$f[i+1]元，还要加上自己的 $1$1元

所以有

1. $g\left[i\right]+=\frac{i}{n}\left(g\right[i]+f[i]+1)$g[i]+=ni​(g[i]+f[i]+1)
2. $g\left[i\right]+=\frac{n-i}{n}\left(g\right[i+1]+f[i+1]+1)$g[i]+=nn−i​(g[i+1]+f[i+1]+1)

总写下来就是 $g\left[i\right]=\frac{i}{n}\left(g\right[i]+f[i]+1)+\frac{n-i}{n}\left(g\right[i+1]+f[i+1]+1)$g[i]=ni​(g[i]+f[i]+1)+nn−i​(g[i+1]+f[i+1]+1)

将其化简得到
$g\left[i\right]=\frac{i}{n-i}f\left[i\right]+g[i+1]+f[i+1]+\frac{n}{n-i}$g[i]=n−ii​f[i]+g[i+1]+f[i+1]+n−in​

初值 $g\left[n\right]=0$g[n]=0，答案为 $g\left[0\right]$g[0]
应逆向循环

$Code$Code

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年07月22日 星期一 16时43分11秒 *******************************/
#include <cstdio>
#include <fstream>
#define ll long long
using namespace std;
const int maxn = 10004;
//{{{cin
struct IO{
	template<typename T>
	IO & operator>>(T&res){
		res=0;
		bool flag=false;
		char ch;
		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';
		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
		if (flag)	 res=~res+1;
		return *this;
	}
}cin;
//}}}
int n;
double f[maxn],g[maxn];
//f[i] -> 买到i种邮票后，离买到n种邮票的期望还差天数
//g[i] -> 拥有(不是买)i种邮票， 买到n种邮票的期望花费
int main()
{
	cin>>n;
	f[n]=0,g[n]=0;
	for (int i=n-1;i>=0;--i)	f[i]=f[i+1]+1.0*n/(n-i);
	for (int i=n-1;i>=0;--i)	g[i]=1.0*i/(n-i)*f[i]+g[i+1]+f[i+1]+1.0*n/(n-i);
	printf("%.2lf\n",g[0]);
	return 0;
}

本篇博客亦被收进期望总结
双倍经验:
题目链接[POJ3682]King Arthur’s Birthday Celebration
代码

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧