1426_牛客博客

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

可以合并当前项的 $d p$ 哦！

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

那么容易得到转移方程:

$f_i=f_i*(i/n)+f_{i+1}*(1-i/n)+1$ .

合并同类项可以得到:

$f_i=f_{i+1}+n/(n-i)$ .

同时定义答案数组 $a n s_{i}$ 已经拿了 $i$ 个所需钱的期望,那么也可以得到方程.

$ans_i=(i/n)*(ans_i+f_i)+(1-i/n)*(ans_{i+1}+f_{i+1})+1$ .

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

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

$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;
}
/*

*/