链接：https://vjudge.net/problem/UVA-11427
思路：由于每天是独立的，所以期望就是一天概率的倒数（很好证明），关键是一天的概率不太好算，因为涉及到当前的状态的判断（即总比例是否超过p），所以我们考虑到了概率中的动态规划。用pp[i][j]表示一共玩了i天赢了j天的状态，i>j是不存在的所以全部为0，然后概率大于p的也全都为0，如果当前i，j概率小于p，那么状态转移pp[i][j] = pp[i-1][j](1-p) + pp[i-1][j-1]p，注意j=0的时候要特殊处理一下即可，最后算0-n的总和，表示这n天总共失败的概率，即可算出成功概率，倒一下就是期望。
代码：
#include<bits/stdc++.h>
using namespace std;
int t,n;
double p;
double pp[110][110];
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int kase = 0;
scanf("%d",&t);
while(t--){
memset(pp,0,sizeof(pp));
int now1,now2;
scanf("%d/%d%d",&now1,&now2,&n);//这种输入方法有点妙学习一下
pp[0][0] = 1;
pp[0][1] = 0;
p = 1.0*now1/now2;
for(int i=1;i<=n;i++){
for(int j=0;j*now2<=i*now1;j++){
pp[i][j] = pp[i-1][j]*(1-p);
if(j)pp[i][j]+=pp[i-1][j-1]*p; //j=0防止越界要特判
}
}
double res = 0;
for(int i=0;now2*i<=n*now1;i++){
res+=pp[n][i];
}
printf("Case #%d: %d\n",++kase,(int)(1/res));
}
return 0;
}
