Rating

误入点分治题单的一个期望dp.
对于这个题来说,我们不妨设置f[i]为i-1分到i分所需要的次数(我们把50分看做1分.),然后他的转移也不难.
对于f[i-1]来说,它可以一步就就到f[i],也可能-2再到f[i],所以概率方程就是:

  f[i]=p+(1-p)*(1+f[i-2]+f[i-1]+f[i]).
->f[i]=1+((1-p)/p)*(1+f[i-2]+f[i-1]).

嗦嘎,如此这个题目就完成了,ans=tot(f[1...20])-f[20].因为答案必定是950,1000的形式.
然后关于初值,也是看这个方程得到的,因为f[0]=0和f[-1]不存在可以看成0,所以f[1]=1/p.然后同理f[2]=1/(p*p).
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=25;
double f[N];
int main() 
{
    double p;
    while(cin>>p)
    {
        double tot=0;
        f[1]=1/p;f[2]=1/(p*p);
        tot+=f[1]+f[2];
        for(int i=3;i<=20;i++)
        {
            f[i]=1+((1-p)/p)*(1+f[i-2]+f[i-1]);
            tot+=f[i];
        }printf("%.6f\n",tot*2-f[20]);
    }return 0;
}