Millionaire 解题报告
题目大意:
你被邀请到某个电视节目中去玩下面这个游戏。一开始你有X元钱，接着进行M轮赌博。每一轮，可以将所持的任意一部分钱作为赌注。赌注不光可以是整数，也可以是小数。一分钱不押或全部都押都没有关系。每一轮都有P的概率可以赢，赢了赌注就会翻倍，输了赌注就没了。如果你最后持有1000000元以上的钱的话，就可以把这些钱带回家。请计算当你采取最优策略时，获得1000000元以上的钱并带回家的概率。
限制条件
0≤P≤1.0
1≤X≤1000000
Small
1≤M≤5
Large
1≤M≤15
题目解析:
由于赌注并不一定是整数，所以就有无限种押注方法，也就不能用暴力搜索来做。但是可以换一种思路来看这个问题：我们从最后一轮出发分析，会发现总共有三种情况。
1、如果这时你已经有1000000元以上的钱，那就不用再押注了，直接可以带上钱回家，所以概率=1
2、如果这时你有500000元以上的钱，就全押了，因为如果你最后钱没有达到1000000元以上的话，就不能带上钱回家了，所以只要这一轮赢了你就能带钱回家，输了就不能带钱回家，概率=P
3、如果这时你有不到500000元的钱，那你肯定不能带钱回家了，就算你全押上赢了也不可能达到1000000元以上了，所以概率=0
根据上面的三种情况，我们可以发现，虽然赌注可以有无限种可能，但概率其实是一个阶梯函数，即一个区间范围对应一个概率。
然后再根据最后一轮的分析，计算出倒数第二轮的各种区间状态下的概率，再计算出倒数第三轮的各种区间状态下的概率.....直到计算出第一轮各种区间状态下的概率。
综上，总的算法思想是:
从倒数第一轮出发(共三种区间状态)，计算出倒数第i轮下，各种区间状态下最后能回家的概率，逐步推导计算出倒数第M轮，即第一轮时，各种区间状态下，最后能回家的概率，然后只要根据初始金额X，找到相应的区间状态，就能知道最后能回家的概率是多少。
Code:
/*
*算法来自《挑战程序设计竞赛》，注释 by Jorbe
*date:2013.12.10
*/
//输入
int M,X;
double P;
double dp[2][(1<<MAX_M)+1];
void solve(){
int n=1<<M;
double *pre=dp[0],*nxt=dp[1];
memset(prv,0,sizeof(double)*(n+1));
prv[n]=1.0; //即当金额>=1000000时的概率
for(int r=0,r<M;r++){ //共M轮，是从倒数第一轮开始计算区间状态概率的
for(int i=0;i<n;i++){ //共2^M+1种区间状态
int jub=min(i,n-i); //最多只要计算n/2次各种押注策略下的概率，否则i+j>n
double t=0.0;
for(int j=0;j<=jub;j++){ //计算各种押注策略下的概率，然后取最大值(最优策略)
t=max(t,P*prv[i+j]+(1-p)*prv[i-j]); //计算押注为j时的概率
}
nxt[i]=t; //保持当前区间状态下，使用最优押注策略时的概率值
}
swap(prv,nxt); //交换prv、nxt值，使当前这轮计算所得各种区间状态概率，作为下一轮初始数据
}
int i=(ll)X*n/1000000; //计算出初始金额X在第几块区间状态 n/1000000=i/X
printf("%.6f\n",prv[i]); //输出相应区间状态的概率值
}