题意: n面骰子掷m次,求最大值的期望.
别人的做法:最大值为i的概率=所有点数<=i的概率-所有点数<=i-1的概率,然后直接算.
sb做法:精度要求1e-4,而m较大时最大值是一个较小数的概率非常小,精度范围内不影响答案,所以直接dp,f[i][j]表示掷了i次之后最大值为j的概率,通过前缀和优化做到O(n)转移
方程为f[i][j]=(f[i-1][1]+f[i-1][2]+f[i-1][3]+….+f[i][j-1])*(1/n)+f[i-1][j]*(j/n)
因为点数越小概率越小所以不考虑较小的项.防止WA所以在不超时的前提下使用尽可能高的精度.
#include<cstdio> #include<algorithm> using namespace std; //#include<ctime> const int maxn=100005; double p[2][maxn]; double pre[maxn]; int n; int m; void init(int m){ // double t1=clock(); for(int i=1;i<=n;++i){ p[0][i]=1.0/n; } int flag=1; int lim=0; for(int j=1;j<=m;++j){//if(j%1000==0)printf("%d ",j); double pre=0; for(int i=lim+1;i<=n;++i){ pre+=p[flag^1][i-1]; p[flag][i]=p[flag^1][i]*i/n+pre/n; if(p[flag][i]<1e-16)lim=i; } flag^=1; } // double t2=clock(); } double f(int m){ double ans=0; for(int i=1;i<=n;++i){ ans+=i*p[m][i]; } return ans; } int main(){ scanf("%d%d",&n,&m); init(m); printf("%.5f ",min(f(0),f(1))); return 0; }