bzoj 1426: 收集邮票【期望dp】

我太菜了，看的hzwer的blog才懂

大概是设f[i]表示已经拥有了i张邮票后期望还要买的邮票数，这个转移比较简单是f[i]=f[i]*(i/n)+f[i+1]*((n-i)/n)+1

然后设g[i]为还需要的钱，可以把转移看做每张票都比前面的贵1元，就是g[i]=((n-i)/n)*(g[i+1]+f[i+1])+(i/n)*(g[i]+f[i])+1

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1000005;

double n,f[N],g[N];

int main()

{

	scanf("%lf",&n);

	for(int i=n-1;i>=0;i--)

	   f[i]=f[i+1]+n/(n-i);

	for(int i=n-1;i>=0;i--)

	   g[i]=g[i+1]+f[i+1]+(n*i)/((n-i)*n)*f[i]+n/(n-i);

	printf("%.2lf",g[0]);

    return 0;

}

巴特西

bzoj 1426: 收集邮票【期望dp】

最新文章

热门文章