大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
Rating
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 414 Accepted Submission(s): 261
Special Judge
1.000000 0.814700
39.000000 82.181160
题目:一个女孩打比赛,每次比赛结果若在前200名则能给她的rating加上50分,否则将会将去100分(rating最小为0,最大为1000—-可以进入前200的概率为p)。为了可以达到1000分。这个女孩使用两个帐号进行比赛,每次使用rating低的那个帐号比赛,直到有一个帐号rating达到1000。给定一个p。问最后须要进行比赛场数的期望值。
题解:首先我们想到的是推公式,以dp[i]代表从i*50-(i+1)*50的期望值。dp[0]和dp[1]须要单独处理。
dp[0]代表我们从0-50须要进行的场数,分成两种情况:1.成功,概率为p,期望为1*p
2.失败。概率1-p。期望为(1-p)*(1+dp[0])
—–所以dp[0]=1*p+(1-p)*(1+dp[0]) ,化简后dp[0]=1/p;
dp[1]代表我们从50-100的场数期望,分成两种情况:1.成功,概率为p,期望为1*p
2.失败,概率1-p,期望为(1-p)*(1+dp[0]+dp[1])
—–所以dp[1]=1*p+(1-p)*(1+dp[0]+dp[1]) ,化简后dp[1]=1+(1-p)/p*(1+dp[0]);
i>2,dp[i]的求法,分成两种情况:1.成功,概率为p。期望为1*p
2.失败,概率1-p,期望为(1-p)*(1+dp[i-2]+dp[i-1]+dp[i])
—–所以dp[i]=1*p+(1-p)*(1+dp[i-2]+dp[i-1]+dp[i]) 。化简后dp[i]=1+(1-p)/p*(1+dp[i-2]+dp[i-1]);
这样,由于要使用两个帐号进行比赛,所以我们最后到达的状态就是一个帐号rating=1000,另外一个=950,仅仅须要进行dp求和即可了。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int main() { double p,q; double dp[20]; while(cin>>p) { memset(dp,0,sizeof(dp)); q=1.0-p; double sum=0; dp[0]=1.0/p; dp[1]=1.0+q/p*(1+dp[0]); sum+=(dp[0]+dp[1])*2; for(int i=2;i<=19;i++) { dp[i]=1.0+q/p*(1+dp[i-1]+dp[i-2]); sum+=dp[i]*2; } printf("%.6lf\n",sum-dp[19]); } return 0; }
高斯消元的做法(公式同上):
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; const double eps=1e-11; //设置为1e-9时Wa了 double a[40][40],x[40]; int equ,var; void Debug() { for(int i=0; i<equ; i++) { for(int j=0; j<=var; j++) printf("%4.2lf ",a[i][j]); puts(""); } puts(""); } double Gauss() { int k,col,max_r; for(k=0,col=0; k<equ&&col<var; k++,col++) { max_r=k; for(int i=k+1; i<equ; i++) if(fabs(a[i][col])>fabs(a[max_r][col])) max_r=i; if(max_r!=k) for(int i=0; i<=var; i++) { swap(a[max_r][i],a[k][i]); } if(fabs(a[k][col])<eps) { k--; continue; } for(int i=k+1; i<equ; i++) { if(fabs(a[i][col])>eps) { double t=a[i][col]/a[k][col]; for(int j=col; j<=var; j++) { a[i][j]=a[i][j]-a[k][j]*t; } } } } //Debug(); double ans=0; for(int j=var-1; j>=0; j--) { double temp=a[j][var]; for(int r=j+1; r<var; r++) temp=(temp-a[j][r]*x[r]); x[j]=temp/a[j][j]; } for(int j=0; j<var; j++) ans+=2.0*x[j]; return ans-x[19]; } void init(double p) { equ=var=20; memset(a,0,sizeof(a)); memset(x,0,sizeof(x)); for(int i=0; i<20; i++) { a[i][var]=1.0; } a[0][0]=p; a[1][0]=p-1; a[1][1]=p; for(int i=2; i<=19; i++) { a[i][i]=p; a[i][i-1]=p-1; a[i][i-2]=p-1; } //Debug(); } int main() { double p; while(scanf("%lf",&p)!=EOF) { init(p); printf("%.6lf\n",Gauss()); } return 0; }
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116993.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...