学步园

首先看一个问题，当p为定值时，

则以d[ i ] 表示已经答对 i 题，后的最大期望值 d[ i ] = max(2^i , d[ i+1 ] * p);

则改题目结果为 d[ i ] 在 t - 1 上积分，由于其为均匀分布，积分很好积，还有一个问题 第一开始认为 p 的期望为 （1+t）/2； 直接用该值计算了，但其与上述积分式并不等价

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
long long c[41];
double d[45];
int main()
{
  c[0]=1;
  for(int i=1;i<=40;i++) c[i]=c[i-1]*2;
  double t,p0;
  int n;
  while(scanf("%d %lf",&n,&t)==2){
       if(!n) break;
       d[n]=c[n];
       for(int i=n-1;i>=0;i--){
           double p0 = max(t,c[i]/d[i+1]);
           double p1 = (p0-t)/(1-t);
           d[i]=p1*c[i]+(1.0 - p1)*(p0+1)/2.0*d[i+1];
       }
       printf("%.3lf\n",d[0]);
  }
  return 0;
}