有 个人,最开始每个人手中有 颗绿宝石,每天晚上,会随机选一个绿宝石分裂为两个。
求 个晚上后绿宝石数量最多的 个人的绿宝石数和的期望值。
,。
设 表示把 划分成 个有标号非负整数相加的方案数,转移考虑枚举 的数的个数:
设 表示把 划分成 个有标号非负整数相加的所有方案中前 大的数的和,转移类似:
最后答案即为 ,由于神秘原因,所以开 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;
}