相当于在不同模块之间来回移动
#include<cstdio> #include<iostream> #include<cstring> using namespace std; //最大可能的模块数 const int maxn = 1 << 15 + 10; //轮数 int M; //赌赢概率 double P; //本钱 int X; //dp[i][j] 表示第i轮每个模块赢到100W的概率 //这里采用滚动数组节约内存 double dp[2][maxn]; //新技能get， 滚动数组 double *prv = dp[0], *nxt = dp[1]; int main () { memset(dp, 0, sizeof(dp)); cin >> M >> P >> X; int n = 1 << M; prv[n] = 1.0; for(int i= 0; i< M; i++){ for(int j= 0; j<= n; j++){ int ub = j > n-j ? n-j : j; double temp = 0.0; //枚举可能跨越的模块的数 for(int k= 0; k<= ub; k++) if(temp < P*prv[j+k] + (1-P)*prv[j-k]) //这把赌赢的概率*赌赢后赢到100W的概率 //这把赌输的概率*赌输后赢到100W的概率 temp = P*prv[j+k] + (1-P)*prv[j-k]; nxt[j] = temp; } //新技能get， 滚动数组 swap(prv, nxt); } //判断 X 在哪个模块中 int pos = (double) X / 1000000 * n; printf("%f\n", prv[pos]); return 0; }
