【數學+機率+期望】HDU-1145 So you want to be a 2n-aire?

注解

1、初始值為1，如果答一個題後平均能達到的金額大于不答此題手裡的金額，就應該答，否則就不應該答。

2、每答對1題翻倍，是以答n個題後全對應該是2的n次方。

3、求答與不答的機率邊界，也就是bestMoney[i]/expected[i+1];，其實也就是0.5

4、答題機率是[t,1]，如果t>0.5，顯然應該答。答的機率是[t,1]之間的數，取期望，也就是(t+1)/2。而如果t<0.5，在[t,0.5]之間時應該不答，在[0.5,1]之間時應該答。是以期望是(0.5-t)/(1-t)*不答+0.5/(1-t)*答，不答的話，手裡的金額就是bestmoney[i]（因為i表示第一個不答的題），答的話，就是expected[i+1]乘上答的機率：（1+0.5) / 2

5、應該從後往前倒着求，也就是從n-1到0，最後輸出的是expected[0]。

代碼

#include <iostream>

using namespace std;

const int MAXN = 32;

double expected[MAXN];
double bestMoney[MAXN];
int n;
double t;

void prework(){
    bestMoney[0] = 1;
    for(int i=1; i<MAXN; i++){
        bestMoney[i] = bestMoney[i-1] * 2;
    }
}

void mainwork(){
    expected[n] = bestMoney[n];
    for(int i=n-1; i>=0; i--){
        double boundary = bestMoney[i]/expected[i+1];
        if(boundary<=t){
            expected[i] = (1.0+t)/2 * expected[i+1];
        }
        else{
            expected[i] = (boundary-t)/(1.0-t) * bestMoney[i] + (1-boundary)/(1-t) * (1+boundary)/2.0 * expected[i+1];
        }
    }
}

void print(){
    printf("%.3lf\n", expected[0]);
}

int main() {
    
    prework();
     
    cin>>n>>t;
    while(n || t){
        mainwork();
        print();
        cin>>n>>t;
    }

    return 0;
}
           

結果