首页 > 代码库 > 【BZOJ 2318】 2318: Spoj4060 game with probability Problem(概率DP)

【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

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

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

Input

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

对于每组数据,一行三个数npq

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\n",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\n",f[n][0]);
31     }
32     return 0;
33 }
View Code

 

2017-04-22 10:17:55

【BZOJ 2318】 2318: Spoj4060 game with probability Problem(概率DP)