2318: Spoj4060 game with probability Problem
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 371 Solved: 173Description
Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。
现在Alice先手投掷硬币，假设他们都想赢得游戏，问你Alice胜利的概率为多少。
Input
第一行一个正整数t，表示数据组数。
对于每组数据，一行三个数n，p，q。
Output
对于每组数据输出一行一个实数，表示Alice胜利的概率，保留6位小数。
Sample Input
11 0.5 0.5
Sample Output
0.666667HINT
数据范围：
1<=t<=50
0.5<=p,q<=0.99999999
对于100%的数据 1<=n<=99999999
Source
【分析】
这种题的特点是转移成环，一般来说要消元。不过这题转台转移量少，可以手动消元。
打了两种打法:
1、【我自己的方法】
f[i][0]表示0作为先手，面对i个棋子，0获胜概率。
f[i][1]表示1作为先手，面对i个棋子，1获胜概率。
f[i][0]=1-p*min(f[i][1],f[i-1][1])-(1-p)*max(f[i][1],f[i-1][1])
f[i][1]=1-q*min(f[i][0],f[i-1][0])-(1-q)*max(f[i][0],f[i-1][0])
但是这里有min和max，不能直接移项。共有四种情况，每种情况都算一下，然后判断这个min和max是否成立。
【其实会不会有多解sm的呢？我也不清楚，但是答案肯定是符合的。。至于为什么只有答案符合，我也不会证明。但是这样是可以过的。
【其实主要是这样判断，最值里面有不确定因素，其实判断f[i-1][0]和1-f[i-1][1]也是可以的，就不用枚举4种情况那么麻烦了
代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1100 double f[Maxn][]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
double p,q;
scanf("%d%lf%lf",&n,&p,&q);
n=min(n,);
f[][]=f[][]=;
for(int i=;i<=n;i++)
{
double A0=f[i-][],A1=f[i-][],P,Q;
//x0=1-P*x1-(1-P)*A1
//x1=1-Q*x0-(1-Q)*A0
P=p,Q=q;
f[i][]=(-P+P*(-Q)*A0-(-P)*A1)/(-P*Q);
f[i][]=(-Q+Q*(-P)*A1-(-Q)*A0)/(-P*Q);
if(f[i][]<=A1&&f[i][]<=A0) continue;
P=p,Q=-q;
f[i][]=(-P+P*(-Q)*A0-(-P)*A1)/(-P*Q);
f[i][]=(-Q+Q*(-P)*A1-(-Q)*A0)/(-P*Q);
if(f[i][]<=A1&&f[i][]>=A0) continue;
P=-p,Q=q;
f[i][]=(-P+P*(-Q)*A0-(-P)*A1)/(-P*Q);
f[i][]=(-Q+Q*(-P)*A1-(-Q)*A0)/(-P*Q);
if(f[i][]>=A1&&f[i][]<=A0) continue;
P=-p,Q=-q;
f[i][]=(-P+P*(-Q)*A0-(-P)*A1)/(-P*Q);
f[i][]=(-Q+Q*(-P)*A1-(-Q)*A0)/(-P*Q);
}
printf("%.6lf\n",f[n][]);
}
return ;
}
2、第二种方法是看别人的，代码量比我少一点。
但是我一般不会这样表示的说。
f[i][0]表示0面对i，0获胜概率。f[i][1]表示1面对i，0获胜概率。
那么当f[i-1][0]>f[i-1][1]，当面对i时，0肯定想拿石子，1肯定不想。
反之不说了。
f[i][0]=p*f[i-1][0]+(1-p)*f[i][1]
f[i][1]=q*f[i-1][1]+(1-q)*f[i][0]
反之
f[i][0]=(1-p)*f[i-1][0]+p*f[i][1]
f[i][1]=(1-q)*f[i-1][1]+q*f[i][0]
移项消元即可。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1100 double f[Maxn][]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
double p,q;
scanf("%d%lf%lf",&n,&p,&q);
n=min(n,);
f[][]=;f[][]=;
for(int i=;i<=n;i++)
{
double A0=f[i-][],A1=f[i-][],P,Q;
if(A0<=A1) P=-p,Q=-q;
else P=p,Q=q;
f[i][]=(A1*(-P)+A0*(-Q)*P)/(-P*Q);
f[i][]=(A0*(-Q)+A1*(-P)*Q)/(-P*Q);
}
printf("%.6lf\n",f[n][]);
}
return ;
}
2017-04-22 10:17:55