【BZOJ 2318】 2318: Spoj4060 game with probability Problem（概率DP）

2318: Spoj4060 game with probability Problem
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 371 Solved: 173
Description

Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。

现在Alice先手投掷硬币，假设他们都想赢得游戏，问你Alice胜利的概率为多少。

Input

第一行一个正整数t，表示数据组数。

对于每组数据，一行三个数n，p，q。

Output

对于每组数据输出一行一个实数，表示Alice胜利的概率，保留6位小数。

Sample Input

1

1 0.5 0.5

Sample Output

0.666667

HINT

数据范围：

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种情况那么麻烦了

　　代码：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define Maxn 1100
 8 
 9 double f[Maxn][2];
10 
11 int main()
12 {
13     int T;
14     scanf("%d",&T);
15     while(T--)
16     {
17         int n;
18         double p,q;
19         scanf("%d%lf%lf",&n,&p,&q);
20         n=min(n,1000);
21         f[0][1]=f[0][0]=0;
22         for(int i=1;i<=n;i++)
23         {
24             double A0=f[i-1][0],A1=f[i-1][1],P,Q;
25             //x0=1-P*x1-(1-P)*A1
26             //x1=1-Q*x0-(1-Q)*A0
27             P=p,Q=q;
28             f[i][0]=(1-P+P*(1-Q)*A0-(1-P)*A1)/(1-P*Q);
29             f[i][1]=(1-Q+Q*(1-P)*A1-(1-Q)*A0)/(1-P*Q);
30             if(f[i][1]<=A1&&f[i][0]<=A0) continue;
31             P=p,Q=1-q;
32             f[i][0]=(1-P+P*(1-Q)*A0-(1-P)*A1)/(1-P*Q);
33             f[i][1]=(1-Q+Q*(1-P)*A1-(1-Q)*A0)/(1-P*Q);
34             if(f[i][1]<=A1&&f[i][0]>=A0) continue;
35             P=1-p,Q=q;
36             f[i][0]=(1-P+P*(1-Q)*A0-(1-P)*A1)/(1-P*Q);
37             f[i][1]=(1-Q+Q*(1-P)*A1-(1-Q)*A0)/(1-P*Q);
38             if(f[i][1]>=A1&&f[i][0]<=A0) continue;
39             P=1-p,Q=1-q;
40             f[i][0]=(1-P+P*(1-Q)*A0-(1-P)*A1)/(1-P*Q);
41             f[i][1]=(1-Q+Q*(1-P)*A1-(1-Q)*A0)/(1-P*Q);
42         }
43         printf("%.6lf
",f[n][0]);
44     }
45     return 0;
46 }

View Code

　　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]

　　移项消元即可。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define Maxn 1100
 8 
 9 double f[Maxn][2];
10 
11 int main()
12 {
13     int T;
14     scanf("%d",&T);
15     while(T--)
16     {
17         int n;
18         double p,q;
19         scanf("%d%lf%lf",&n,&p,&q);
20         n=min(n,1000);
21         f[0][0]=0;f[0][1]=1;
22         for(int i=1;i<=n;i++)
23         {
24             double A0=f[i-1][0],A1=f[i-1][1],P,Q;
25             if(A0<=A1) P=1-p,Q=1-q;
26             else P=p,Q=q;
27             f[i][0]=(A1*(1-P)+A0*(1-Q)*P)/(1-P*Q);
28             f[i][1]=(A0*(1-Q)+A1*(1-P)*Q)/(1-P*Q);
29         }
30         printf("%.6lf
",f[n][0]);
31     }
32     return 0;
33 }

View Code

2017-04-22 10:17:55