每天晚上你都玩纸牌游戏，如果第一次就赢了就高高兴兴地去睡觉，如果输了就继续玩。假设每盘游戏你获胜地概率都是p，且各盘游戏的输赢都是独立的。你是一个固执的完美主义者，因此会一直玩到当晚获胜局面的比例严格大于p时才停止，然后高高兴兴地去睡觉。当然，晚上的时间有限，最多只能玩n盘游戏，如果获胜比例一直不超过p的话，你只能垂头丧气地去睡觉，以后再也不玩纸牌了。你的游戏是计算出平均情况下，你会玩多少个晚上的纸牌。
设一局胜率为p，则败率为q=1-p
第一步：求单一一天能达成目标快快乐乐去睡觉的概率，设为P
第二步：求该游戏能玩几天的期望，即无穷级数 $sumlimits_{i=1}^infty i*P^{i-1}*(1-P)$，可以发现这个无穷级数等于$frac {1} {1-P}$
问题是P怎么求，我一直在想P关于n，p的数学表达式，想不出来，看了题解发现这种题是dp
设单一一天目标未达成概率为Q，即Q=1-P，如果目标未达成，他必玩了n局，而且如果设总共胜了x局，那么必须$frac {x} {n} leqslant p$，所有胜x局的局面都未达成目标，他们的出现概率之和即为Q
设dp[i,j]表示玩了i局胜了j局的‘目标未达成的’局面出现的概率（注：我们要求的是目标未达成的局面出现的概率，而目标未达成的局面的前一个局面一定也是目标未达成的局面），即这里dp的‘局面’全部都是满足$frac {j} {i} leqslant p$的局面，则转移方程为dp[i,j]=dp[i-1,j]*q+dp[i-1,j-1]*p
最后Q即为dp[n,x]之和，输出1/Q就完事了
#include<bits/stdc++.h> using namespace std; int N,a,b,n; double p,Q; double dp[100+10][100+10]; int main(){ cin>>N; for(int t=1;t<=N;t++){ scanf("%d/%d%d",&a,&b,&n); p=(double)a/(double)b; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=0; dp[1][0]=1.0-p; //边界 //求当晚失败概率Q //dp[i,j] 局面i局中赢了j局'出现'的概率 注意：j/i<=p //dp[i,j]=dp[i-1,j]*q+dp[i-1,j-1]*p 注意：j/i<=p要一直成立 //边界 dp[1,0] Q=0; for(int i=2;i<=n;i++){ for(int j=0;(double)j<=p*(double)i;j++){ dp[i][j]+=(p*dp[i-1][j-1]+(1.0-p)*dp[i-1][j]); } } for(int i=0;(double)i<=p*(double)n;i++){ Q+=dp[n][i]; } int ans=1.0/Q; printf("Case #%d: %d ",t,ans); } return 0; }
那么这个P到底有没有数学表达式呢？？