首页 > 代码库 > HDOJ 1145 So you want to be a 2n-aire? 期望DP

HDOJ 1145 So you want to be a 2n-aire? 期望DP

2024-11-23 11:44:39   202人阅读


期望DP

So you want to be a 2n-aire?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 267    Accepted Submission(s): 197


Problem Description
The player starts with a prize of $1, and is asked a sequence of n questions. For each question, he may 
quit and keep his prize. 
answer the question. If wrong, he quits with nothing. If correct, the prize is doubled, and he continues with the next question. 
After the last question, he quits with his prize. The player wants to maximize his expected prize. 
Once each question is asked, the player is able to assess the probability p that he will be able to answer it. For each question, we assume that p is a random variable uniformly distributed over the range t .. 1. 
 

Input
Input is a number of lines, each with two numbers: an integer 1 ≤ n ≤ 30, and a real 0 ≤ t ≤ 1. Input is terminated by a line containing 0 0. This line should not be processed.
 

Output
For each input n and t, print the player‘s expected prize, if he plays the best strategy. Output should be rounded to three fractional digits.
 

Sample Input
1 0.5
1 0.3
2 0.6
24 0.25
0 0
 

Sample Output
1.500
1.357
2.560
230.138
 

Source
University of Waterloo Local Contest 2005.09.17
 

Recommend
Eddy   |   We have carefully selected several similar problems for you:  1148 1147 1146 1144 1152 
 


/* ***********************************************
Author        :CKboss
Created Time  :2015年01月29日 星期四 22时37分28秒
File Name     :UVA10900.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

int n;
double dp[100];
double t;

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	while(scanf("%d%lf",&n,&t)!=EOF)
	{
		if(n==0) break;
		memset(dp,0,sizeof(dp));
		dp[n]=(1<<n);
		for(int i=n-1;i>=0;i--)
		{
			double p0=max(t,(1<<i)/dp[i+1]);
			double p1=(p0-t)/(1-t);
			dp[i]=(1<<i)*p1+((1+p0)/2*dp[i+1]*(1-p1));
		}
		printf("%.3lf\n",dp[0]);
	}
    return 0;
}



HDOJ 1145 So you want to be a 2n-aire? 期望DP


联系
我们