hdu 1145.So you want to be a 2^n-aire？
http://acm.hdu.edu.cn/showproblem.php?pid=1145
So you want to be a 2 n-aire？
Time Limit：2000/1000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：94 Acceepted Submission(s)：72
Problem Description
The player starts with a prze of$1、and is asked a sequence of n questions.For each question、he may
quit and keep his prze.
answer the question.If wrong，he quits with nothing.If corect，the prze is doubled，and he continues with the next question.
After the last question、he quits with his prze.The player wants to maximize his expected prze.
Onece each question is asked，t he play is able to assis the probability a that he will be able to answer it.For each question，we assie that p is a random variable unormly stributed over the rand.1.
Input
Input is a number of lines、each with two numbers：a n integer 1≦n≦30、and a real 0≦t≦1.Input is terminated by line containing 0.This line shoud not be processed.
Output
For each input n and t，print t he player's expected prinze，if he plass the best strate.Output shound be rounded to three fractional digits.
Sample Input
1 0.5
1 0.3
2 0.6
24 0.25
0
Sample Output
1.5,000
1.357
2.560
23.138
ソurce
University of Waterloo Local Contast 2005.9.17
件名:
最初は1ドルで、1ラウンドごとに現在のお金を受け取ってゲームから退出するか、または継続ゲームを選択して、お金のdoubleを勝ちました。さもなければ0ドルでゲームが終了し、勝つ確率は[t.1]に分布します。
大体の考え:
実は私自身は何の考えもありません。題解は紫色です。
f[i]はn-iラウンド後の最大金額を表します。f[0]=2
n
第iラウンドに対しては放棄しないといけません。
iドルです。pの機会がなければf[i-1]があります。
pは[t-1]に分布しているので、確率密度は1/(1-t)であり、その後max(p**f[i]，2
n-i）dp積分
つまりf[i]=1/(1-t)*int^1(max(p*f[i]，2
n-i)dp) (int^1(f(x)dx)はf(x)に対して一重の積分です。)
実はこのdp方程式はまだ分かりにくいです。いつも問題があるようです。
コード:
So you want to be a 2 n-aire？
Time Limit：2000/1000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：94 Acceepted Submission(s)：72
Problem Description
The player starts with a prze of$1、and is asked a sequence of n questions.For each question、he may
quit and keep his prze.
answer the question.If wrong，he quits with nothing.If corect，the prze is doubled，and he continues with the next question.
After the last question、he quits with his prze.The player wants to maximize his expected prze.
Onece each question is asked，t he play is able to assis the probability a that he will be able to answer it.For each question，we assie that p is a random variable unormly stributed over the rand.1.
Input
Input is a number of lines、each with two numbers：a n integer 1≦n≦30、and a real 0≦t≦1.Input is terminated by line containing 0.This line shoud not be processed.
Output
For each input n and t，print t he player's expected prinze，if he plass the best strate.Output shound be rounded to three fractional digits.
Sample Input
1 0.5
1 0.3
2 0.6
24 0.25
0
Sample Output
1.5,000
1.357
2.560
23.138
ソurce
University of Waterloo Local Contast 2005.9.17
件名:
最初は1ドルで、1ラウンドごとに現在のお金を受け取ってゲームから退出するか、または継続ゲームを選択して、お金のdoubleを勝ちました。さもなければ0ドルでゲームが終了し、勝つ確率は[t.1]に分布します。
大体の考え:
実は私自身は何の考えもありません。題解は紫色です。
f[i]はn-iラウンド後の最大金額を表します。f[0]=2
n
第iラウンドに対しては放棄しないといけません。
iドルです。pの機会がなければf[i-1]があります。
pは[t-1]に分布しているので、確率密度は1/(1-t)であり、その後max(p**f[i]，2
n-i）dp積分
つまりf[i]=1/(1-t)*int^1(max(p*f[i]，2
n-i)dp) (int^1(f(x)dx)はf(x)に対して一重の積分です。)
実はこのdp方程式はまだ分かりにくいです。いつも問題があるようです。
コード:
#include
#include
#include
#include
#include
using namespace std;
#define MAXN
#define eps (1e-8)
#define INF 1000000000
#define abs(x) ( (x) > 0? (x): -(x) )
#define sqr(x) ((x) * (x))
#define MAX(a, b) ((a) > (b)? (a): (b))
#define MIN(a, b) ((a) < (b)? (a): (b))
typedef long long LL;
int n;
double t;
void swap( int &x, int &y ) { int temp = x; x = y; y = temp; }
int main()
{
while ( scanf( "%d%lf", &n, &t ) != EOF && n )
{
double f, g;
f = (double)( 1 << n );
for ( int i = 1; i <= n; ++i )
{
double p = ( 1 << ( n - i ) ) / f;
if ( p < t )
g = ( 1 + t ) / 2 * f;
else if ( p > 1 )
g = ( 1 << ( n - i ) );
else
g = 1 / ( 1 - t ) * ( ( p - t ) * ( 1 << ( n - i ) ) + ( 1 - sqr(p) ) / 2 * f );
f = g;
}
printf( "%.3lf
", f );
}
return 0;
}