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
思路： 將最后一場賭局開始時的錢數分成三段，0~500000，500000~1000000，1000000以上。第一段贏得概率為0，第二段為P，第三段為1。 依此類推，第一局分段最多，為2^M+1。因此，可將錢數分為2^M+1段，任何一局每一段內的贏率相同。從最后一局開始向前遞推，每局開始時錢數為j段，結束時為j+k（贏）或j-k（輸）,概率為P和1-P。
動態方程：dp[i][j] = max(dp[i][j], P*dp[i+1][j+k] + (1 - P)*dp[i+1][j-k]) dp[i][j]為第i場賭局開始時錢數為j段的情況下贏的概率。
由于每一次概率的更新只與下一場賭局（i+1）有關，所以可以設兩個一維數組交換進行，可以節省內存。 動態方程：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場結束時擁有的錢數在j區間 double st[1<<15 + 2]; // 第i場開始時擁有的錢數在j區間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個區：0~1000000/n，1000000/n~2*1000000/n...(n-1)*1000000/n~1000000，000000以上 若錢數>=1000000可直接帶走，概率1 memset(en, 0, sizeof(en)); memset(st, 0, sizeof(st)); en[n] = 1; //若最后一局結束時錢數在n區間則必贏 for(int i = M; i > 0; i--){ //第i場賭賽（倒著算） for(int j = 0; j <= n; j++){ //本場賭局開始時我擁有的錢數在j區間，這種情況下我最終能贏概率為st[j] int temp = min(j, n - j); //temp為本輪賭局結束時我最多擁有的錢數 //保證2*j <= n，因為錢數到n區間可直接拿走，超出沒有意義，若輸掉賭局可能失去更多錢，不是最優解 st[j] = 0.0; for(int k = 0; k <= temp; k++){ //下一輪賭局拿出k區間的錢數參賭 st[j] = max(st[j], P*en[j + k] + (1 - P)*en[j - k]); //若贏，錢數 = j - k + k*2 = j + k //若輸，錢數 = j - k } } swap(en, st); //本場賭局開始的錢數和上一場賭局結束的錢數相同 } int i = (long long)X*n/1000000; //最初我擁有的錢數在i區間 printf("Case #%d: %.6f/n", a, en[i]); } return 0; }新聞熱點
疑難解答
