[文章目录]
Description
Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。
现在Alice先手投掷硬币，假设他们都想赢得游戏，问你Alice胜利的概率为多少。1<=t<=50；0.5<=p,q<=0.99999999；对于100%的数据 1<=n<=99999999
向概率DP+博弈低头。
设f[i]表示剩i个石子，Alice先手时赢的概率，g[i]表示剩i个石子，Alice后手时赢得概率。
向互相调用然后还取max的概率DP低头。
将f[i]式子中的g[i]迭代，发现,;
然后发现f[i]的值只跟f[i-1]和g[i-1]有关系。
如果f[i-1]>g[i-1]那么，我希望下一个我是先手，那么我就不选当前的。对手同样也有(1-f[i-1])>(1-g[i-1])。所以也不选。
那么状态就确定啦。
n很大。发现当轮数很多时，概率趋近于定值。所以直接取min。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
double p,q,f[10000],g[10000];
int t,n;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%lf%lf",&n,&p,&q); n=min(n,1000);
int i;g[0]=1;f[0]=0;
for(i=1;i<=n;i++)
{
if(f[i-1]>g[i-1])
{
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);
}
else
{
f[i]=(p*g[i-1]+(1.0-p)*q*f[i-1])/(1.0-(1.0-q)*(1.0-p));
g[i]=(q*f[i-1]+(1.0-q)*p*g[i-1])/(1.0-(1.0-q)*(1.0-p));
}
}
printf("%.6lf\n",f[n]);
}
return 0;
}