hdu 4870

缺乏、安全感 2022-09-20 15:26 91阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=4870][http_acm.hdu.edu.cn_showproblem.php_pid_4870]

题目大意：现在有2个账号，每次拿出分数低的账号去比赛，有p的概率+50分，反之-100分，求到1000分需要比赛次数的数学期望。

题解：将所有分数除以50，情况变成+1，-2，到20分。我们用（x,y）表示第一个账号x分，第二个账号y分，这样就会有（0,0）~（20，19）共210种状态，我们的过程肯定是（0,0）->(1,0)->(1,1)->(2,1)->.......->(20,19)。那么我们发现每次都是一种状态的转移，两个账号可以归为一个账号处理。有两种表示方式，用f\[k\]表示从k分到20分的步数时等式是 f\[k\]=p\*f\[k+1\]+(1-p)\*f\[k-2\]+1，用f\[k\]表示从0分到k分的步数时等式是  f\[k\]=p\*f\[k+1\]+(1-p)\*f\[k-2\]-1，之间+1，-1的区别可以通过画图，第一种看成是从20出发，倒过来推到0。这两种方法都可以解决这题。就第二种方程来说，求出 f\[k\] =1/p+1/p\*f\[k-1\]-(1-p)/p\*f\[k-3\],f\[0\]=0,f\[1\]=1/p,f\[2\]=1/p+1/p^2,从而推出所有的f\[\]。回到2个账号的情况，(0,0)->(1,0)的时候的步数就应该是f\[1\]-f\[0\],(1,0)->(1,1)也是一样，按顺序推下去，累加后得出总和应该是f\[20\]+f\[19\]-2\*f\[0\]，就是最后的答案。

参考博客：[http://www.cnblogs.com/chanme/p/3861766.html][http_www.cnblogs.com_chanme_p_3861766.html]

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int i;
    double p,f[21];
    
    int main()
    {
          while (scanf("%lf",&p)!=EOF)
          {
                f[1]=1/p;
                f[0]=0;
                f[2]=1/p+1/(p*p);
                for (i=3;i<=20;i++)
                {
                      f[i] = 1 / p + 1 / p*f[i - 1] - (1 - p) / p*f[i - 3];
                }
                double ans;
                ans=f[20]+f[19];
                printf("%.6lf\n",ans);
          }
          return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_4870]: http://acm.hdu.edu.cn/showproblem.php?pid=4870
[http_www.cnblogs.com_chanme_p_3861766.html]: http://www.cnblogs.com/chanme/p/3861766.html