HDU 4870 Rating (2014 多校联合第一场 J)(概率)

时间:2022-04-30 05:12:37

题意:

一个人有两个TC的账号,一开始两个账号rating都是0,然后每次它会选择里面rating较小的一个账号去打比赛,每次比赛有p的概率+1分,有1-p的概率-2分,当然如果本身是<=2分的也就还是回到0分。然后问最后其中一个账号到达20分时需要打多少次比赛。

思路:

因为每次50分,到达1000分,所以可以看做每次1分,到达20分
dp[i]表示i到20的数学期望
那么dp[i] = dp[i+1]*p+dp[i-2]*q+1;
令t[i] = dp[i+1]-dp[i]
则t[i] = (t[i+1]*p+t[i-2]*q)
所以t[i+1] = (t[i]-t[i-2]*q)/p

代码:

 #include <iostream>
#include <stdio.h>
using namespace std;
//t[i]为从i分到i+1分需要的比赛次数期望
int main()
{
double t[],dp[];
double p,q,sum;
while(scanf("%lf",&p)!=EOF)
{
sum = ;
q = -p;
t[] = /p;
t[] = t[]/p;
t[] = t[]/p;
sum =t[]+t[]+t[];
for(int i=;i<;i++)
{
t[i]=(t[i-]-t[i-]*q)/p;
sum+=t[i];
}
//sum为一个账号达到20分的平均比赛次数
printf("%.6lf\n",*sum-t[]);//按照比赛规则,一个账号到20分的比赛次数=两个账号到20分的次数减去一个账号从19分到二十分的比赛次数
}
return ;
}