1426

大概这才是期望$dpdp$的入门题吧.

可以合并当前项的$dpdp$哦！

首先定义方程$f_{i}f\_i$表示已经拿到了$ii$个,还需要拿多少次能全部拿完的期望.

那么容易得到转移方程:

$f_i=f_i\ast (i\mathrm{/}n)+f_{i+1}\ast (1-i\mathrm{/}n)+1f\_i=f\_i*(i/n)+f\_\{i+1\}*(1-i/n)+1$.

合并同类项可以得到:

$f_i=f_{i+1}+n\mathrm{/}(n-i)f\_i=f\_\{i+1\}+n/(n-i)$.

同时定义答案数组$an{s}_{i}ans\_i$已经拿了$ii$个所需钱的期望,那么也可以得到方程.

$an{s}_i=(i\mathrm{/}n)\ast (an{s}_i+f_i)+(1-i\mathrm{/}n)\ast (an{s}_{i+1}+f_{i+1})+1ans\_i=(i/n)*(ans\_i+f\_i)+(1-i/n)*(ans\_\{i+1\}+f\_\{i+1\})+1$.

可以理解为提前算好了后面的贡献,使得每件商品的价格变成了$11$.

也可以合并一下同类项得到:

$an{s}_i=i\mathrm{/}(n-i)\ast f_i+an{s}_{i+1}+f_{i+1}+n\mathrm{/}(n-i)ans\_i=i/(n-i)*f\_i+ans\_\{i+1\}+f\_\{i+1\}+n/(n-i)$.

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e4+5;
const int mod=998244353;
const double eps=1e-9;

double f[N],ans[N];

void solve()
{
	int n;
	scanf("%d",&n);
	f[n]=ans[n]=0;
	for(int i=n-1;i>=0;i--)
		f[i]=f[i+1]+(double)n/(double)(n-i);
	for(int i=n-1;i>=0;i--)
		ans[i]=(double)i/(double)(n-i)*f[i]+ans[i+1]+f[i+1]+(double)n/(double)(n-i);
	printf("%.2f\n",ans[0]);
}

int main()
{
	int T=1;
//	scanf("%d",&T);
	while(T--)	solve();
	return 0;
}
/*

*/