P6944 [ICPC2018 WF]Gem Island 做题记录

有 $n$ 个人，最开始每个人手中有 $1$ 颗绿宝石，每天晚上，会随机选一个绿宝石分裂为两个。

求 $d$ 个晚上后绿宝石数量最多的 $r$ 个人的绿宝石数和的期望值。

$1 \le n,d \le 500$，$1 \le r\le n$。

设 $dp_{i,j}$ 表示把 $j$ 划分成 $i$ 个有标号非负整数相加的方案数，转移考虑枚举 $\ge 1$ 的数的个数：

$dp_{i,j}=\sum\limits_{k=1}^{\min(i,j)}\binom{i}{k}dp_{k,j-k}$

设 $pd_{i,j}$ 表示把 $j$ 划分成 $i$个有标号非负整数相加的所有方案中前 $r$ 大的数的和，转移类似：

$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})$

最后答案即为 $\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;
}