题目链接

题意:

一个女孩打比赛，每次比赛结果若在前200名则能给她的rating加上50分，否则将会将去100分（rating最小为0，最大为1000----能够进入前200的概率为p）。为了能够达到1000分，这个女孩使用两个帐号进行比赛，每次使用rating低的那个帐号比赛，直到有一个帐号rating达到1000。给定一个p，问最后需要进行比赛场数的期望值

分析：

这个题本来是高斯消元的题，不过高斯消元的思路有点晕，看了大神的博客，可以用dp来做，

两个账号其实完全不想干, 因为一个账号到1000分时另一个一定是950分

每次50分，到达1000分，所以可以看做每次1分，到达20分

dp[i]---分数i涨到分数i+1的期望 

递推公式：dp[i]=p*1+(1-p)*(dp[i-2]+dp[i-1]+dp[i]+1)    //成功时，需要一步；失败时，浪费一次机会，并且要从i-2涨3次

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]) 

i>2,dp[i]的求法，分成两种情况：1.成功，概率为p，期望为1*p

2.失败，概率1-p，期望为(1-p)*(1+dp[i-2]+dp[i-1]+dp[i])   

所以dp[1]=1*p+(1-p)*(1+dp[0]+dp[1])

所以可以用sum记录两份从0-1000的期望，然后减去d[19]，因为另一个账号只是到了1950.

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #define LL __int64 8 const int maxn = 20+10; 9 using namespace std;10 11 int main()12 {13     double d[maxn], p, q, sum;14     int i;15     while(cin>>p)16     {17         sum = 0;18         q = 1-p;19         d[0] = 1.0/p;20         d[1] = (1.0+q*d[0])/(1.0-q);21         sum += (d[0]+d[1])*2;22         for(i = 2; i < 20; i++)23         {24             d[i] = (1.0+q*d[i-1]+q*d[i-2])/(1.0-q);25             sum += d[i]*2;26         }27         printf("%.6lf\n", sum-d[19]);28     }29     return 0;30 }

hdu 4870 Rating (概率dp)