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;
}