问题 A: Spoj4060 game with probability Problem
时间限制: 1 Sec 内存限制: 128 MB
题目描述
Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。
现在Alice先手投掷硬币，假设他们都想赢得游戏，问你Alice胜利的概率为多少。
输入
第一行一个正整数t，表示数据组数。
对于每组数据，一行三个数n，p，q。
输出
对于每组数据输出一行一个实数，表示Alice胜利的概率，保留6位小数。
样例输入
1
1 0.5 0.5
样例输出
0.666667
提示
数据范围：
1<=t<=50
0.5<=p,q<=0.99999999
对于100%的数据 1<=n<=99999999
设f[i]为还剩i个石头，Alice先手的胜率；g[i]为还剩i个石头，Alice后手的胜率。
考虑逆退，从i-1块转移过来。
分情况考虑.
1，g[i-1]>f[i-1],那么两人都想取得拿下块石头的后手权，那么就要自己拿掉这块石头，对方就成了下一块的先手。但是可能掷不出自己想要的正面。。那么就变成了剩i块石头的后手。
所以 f[i-1]=p*g[i-1]+(1-p)*g[i];
g[i-1]=q*f[i-1]+(1-q)*f[i];
两个联立一下就出来了。
2，f[i-1]>g[i-1],这样就变成了想要在这里后手，那么换一下就行了。
而最初始，g[0]=1,f[0]=0.一个也不剩时先手必输
n太大怎么处理：有人说乘到10000次概率就几乎不变了，而实际上50次就够了。。。落差好大。这种地方就要靠往昔的经验了。
#include <cstdio>
int T,n;double p,q,f[51],g[51];
int main()
{scanf("%d",&T);while(T--){scanf("%d%lf%lf",&n,&p,&q);g[0]=1.0;if(n>50)n=50;for(int i=1;i<=n;i++)if(g[i-1]>f[i-1])f[i]=(p*g[i-1]+(1.0-p)*q*f[i-1])/(p+q-p*q),g[i]=(q*f[i-1]+(1.0-q)*p*g[i-1])/(p+q-p*q);else f[i]=((1.0-p)*g[i-1]+p*(1.0-q)*f[i-1])/(1.0-p*q),g[i]=((1.0-q)*f[i-1]+q*(1.0-p)*g[i-1])/(1.0-p*q);printf("%.6lf\n",f[n]);}
}