PRoblem You have been invited to the popular TV show “Would you like to be a millionaire?”.Of course you would! The rules of the show are simple: Before the game starts, the host spins a wheel of fortune todetermine P, the probability of winning each bet. You start out with some money: X dollars. There are M rounds of betting. In each round, you can bet anypart ****of your current money, including none of it or all of it. The amount is not limited to whole dollars or whole cents. If you win the bet, your total amount of money increases by the amount you bet. Otherwise, your amount of money decreases by the amount you bet.** After all the rounds of betting are done, you get to keep yourwinnings (this time the amount is rounded down to whole dollars) only if you have accumulated
Input The first line of input gives the number of cases, N. Each of the following N lines has the format “M P X”, where: M is an integer, the number of rounds of betting. P is a real number, the probability of winning each round. X is an integer, the starting number of dollars.
Output For each test case, output one line containing “Case #X: Y”, where: X is the test case number, beginning at 1. Y is the probability of becoming a millionaire, between 0 and 1. Answers with a relative or absolute error of at most 10-6 will be considered correct.
Limits 1 ≤ N ≤ 100 0 ≤ P ≤ 1.0, there will be at most 6 digits after the decimal point. 1 ≤ X ≤ 1000000 Small dataset 1 ≤ M ≤ 5 Large dataset 1 ≤ M ≤ 15
思路： 將最后一場賭局開始時(shí)的錢數(shù)分成三段，0~500000，500000~1000000，1000000以上。第一段贏得概率為0，第二段為P，第三段為1。 依此類推，第一局分段最多，為2^M+1。因此，可將錢數(shù)分為2^M+1段，任何一局每一段內(nèi)的贏率相同。從最后一局開始向前遞推，每局開始時(shí)錢數(shù)為j段，結(jié)束時(shí)為j+k（贏）或j-k（輸）,概率為P和1-P。
動態(tài)方程：dp[i][j] = max(dp[i][j], P*dp[i+1][j+k] + (1 - P)*dp[i+1][j-k]) dp[i][j]為第i場賭局開始時(shí)錢數(shù)為j段的情況下贏的概率。
由于每一次概率的更新只與下一場賭局（i+1）有關(guān)，所以可以設(shè)兩個(gè)一維數(shù)組交換進(jìn)行，可以節(jié)省內(nèi)存。 動態(tài)方程：st[j] = max(st[j], P*en[j + k] + (1 - P)*en[j - k])
代碼：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std; double en[1<<15 + 2]; //第i場結(jié)束時(shí)擁有的錢數(shù)在j區(qū)間 double st[1<<15 + 2]; // 第i場開始時(shí)擁有的錢數(shù)在j區(qū)間int main() { int M, X, N; double P; scanf("%d", &N); for(int a = 1; a <= N; a++){ scanf("%d %lf %d", &M, &P, &X); int n = 1<<M; //n = 2^M，將1000000分成n+1個(gè)區(qū)：0~1000000/n，1000000/n~2*1000000/n...(n-1)*1000000/n~1000000，000000以上 若錢數(shù)>=1000000可直接帶走，概率1 memset(en, 0, sizeof(en)); memset(st, 0, sizeof(st)); en[n] = 1; //若最后一局結(jié)束時(shí)錢數(shù)在n區(qū)間則必贏 for(int i = M; i > 0; i--){ //第i場賭賽（倒著算） for(int j = 0; j <= n; j++){ //本場賭局開始時(shí)我擁有的錢數(shù)在j區(qū)間，這種情況下我最終能贏概率為st[j] int temp = min(j, n - j); //temp為本輪賭局結(jié)束時(shí)我最多擁有的錢數(shù) //保證2*j <= n，因?yàn)殄X數(shù)到n區(qū)間可直接拿走，超出沒有意義，若輸?shù)糍€局可能失去更多錢，不是最優(yōu)解 st[j] = 0.0; for(int k = 0; k <= temp; k++){ //下一輪賭局拿出k區(qū)間的錢數(shù)參賭 st[j] = max(st[j], P*en[j + k] + (1 - P)*en[j - k]); //若贏，錢數(shù) = j - k + k*2 = j + k //若輸，錢數(shù) = j - k } } swap(en, st); //本場賭局開始的錢數(shù)和上一場賭局結(jié)束的錢數(shù)相同 } int i = (long long)X*n/1000000; //最初我擁有的錢數(shù)在i區(qū)間 printf("Case #%d: %.6f/n", a, en[i]); } return 0; }新聞熱點(diǎn)
疑難解答
