学步园

题目链接；uva 10900 - So you want to be a 2n-aire?

题目大意：一个答题赢奖金的问题，玩家初始的金额为1，给出n，表示有n道题目，t表示说答对一道题目的概率在t到1之间，每次面对一道题，可以选择结束游戏，获得当前奖金；回答下一道问题，答对的概率p在t到1之间，答对的话奖金翻倍，答错的话结束游戏，没有奖金，求玩家赢的奖金的期望值的最大值。

解题思路：这题的概率是个大坑点啊，因为给的是范围，所以纠结了好久，没做过这种题，看了别人的题解才知道可以用平均值.....假设玩家已经答对了i题，那么他当前的奖金应该是2^i，若答对i+1道题的概率为p， 如果p * ans（下一题的最优期望）>2^i，则说明他一定会选择答题，所以可以先求一下临界概率f = 2 * i/ ans，如果f < t的话，说明无论p为何值（因为p在t~1）都满足p * ans >2 ^i，所以一定回答下一题（这是p去t和1的平均值），如果f>t的话，就要分两种情况讨论，即p在（t~f）的时候，和（f~1），注意两种情况的概率也不相同。

#include <stdio.h>
#include <string.h>
#include <math.h>
const int N = 35;

int n;
double v[N], t;

double solve() {
	if (fabs(1 - t) < 1e-9) return v[n];

	double ans = v[n];
	for (int i = n - 1; i >= 0; i--) {
		double f = v[i] / ans;

		if (f <= t)
			ans  = (1 + t) / 2 * ans;
		else
			ans = (f - t) / (1 - t) * v[i] + (1 - f) / (1 - t) * (1 + f) / 2 * ans;
	}
	return ans;
}

int main () {
	v[0] = 1;
	for (int i = 1; i <= 30; i++)
		v[i] = v[i - 1] * 2;

	while (scanf("%d%lf", &n, &t), n && t) {
		printf("%.3lf\n", solve());
	}
	return 0;
}