P6944 [ICPC2018 WF]Gem Island 做题记录

nn 个人,最开始每个人手中有 11 颗绿宝石,每天晚上,会随机选一个绿宝石分裂为两个。

dd 个晚上后绿宝石数量最多的 rr 个人的绿宝石数和的期望值。

1n,d5001 \le n,d \le 5001rn1 \le r\le n

dpi,jdp_{i,j} 表示把 jj 划分成 ii 个有标号非负整数相加的方案数,转移考虑枚举 1\ge 1 的数的个数:

dpi,j=k=1min(i,j)(ik)dpk,jkdp_{i,j}=\sum\limits_{k=1}^{\min(i,j)}\binom{i}{k}dp_{k,j-k}

pdi,jpd_{i,j} 表示把 jj 划分成 ii个有标号非负整数相加的所有方案中前 rr 大的数的和,转移类似:

pdi,j=k=1min(i,j)(ik)(pdk,jk+min(k,r)×dpk,jk)pd_{i,j}=\sum\limits_{k=1}^{\min(i,j)}\binom{i}{k}(pd_{k,j-k}+\min(k,r)\times dp_{k,j-k})

最后答案即为 pdn,d+rdpn,d\frac{pd_{n,d}+r}{dp_{n,d}},由于神秘原因,所以开 long double 即可。

代码如下:

#include <iostream>
#include <cstdio>

using namespace std;

const int S=505;

int n,d,r;
long double C[S][S],dp[S][S],pd[S][S];

int main()
{
	for(int i=0;i<=S-3;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	scanf("%d%d%d",&n,&d,&r);
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=1;
		for(int j=1;j<=d;j++)
		{
			for(int k=1;k<=i&&k<=j;k++)
			{
				dp[i][j]+=C[i][k]*dp[k][j-k];
				pd[i][j]+=C[i][k]*(pd[k][j-k]+min(k,r)*dp[k][j-k]);
			}
		}
	}
	printf("%Lf\n",pd[n][d]/dp[n][d]+r);
	return 0;
}