BZOJ 2318 【概率DP】

game with probability Problem

[Description]

Alice和Bob在玩一个游戏。有n个石子在这里,Alice和Bob轮流投掷硬币,如果正面朝上,则从n个石子中取出一个石子,否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面,同样,Bob有q的概率投掷出他相投的一面。
现在Alice先手投掷硬币,假设他们都想赢得游戏,问你Alice胜利的概率为多少。

[Solution]

设f[n]为还剩n个石子,Alice先投硬币,Alice的胜率;g[n]为还剩n个石子,Bob先投硬币,Alice的胜率。
我们发现,当Alice此时没有拿当前这个石子,胜率变成了为g[n],若拿了,变成了g[n-1]。
g[n]和g[n-1]分别占有的概率分别可以是p或(1-p)–根据Alice的个人意愿。然而我们发现Alice想赢,而且p>1-p,所以Alice会把p分给g[n]和g[n-1]中大的那个,1-p会给小的那个;相反地,Bob会把q给f[n]/f[n-1]小的那个,1-q给大的。

所以有:
1)$f[n]=p\cdot max(g[n],g[n-1])+(1-p)\cdot min(g[n],g[n-1])$
2)$g[n]=q\cdot min(f[n],f[n-1])+(1-q)\cdot max(f[n],f[n-1])$

分类讨论:
当f[n-1]< g[n-1],根据(1)式,有g[n-1]< f[n]→f[n-1]< f[n];此时若g[n-1]< g[n],因为f[n-1]< g[n]< f[n],又有g[n-1]< f[n]< g[n],推出f[n]和g[n]的关系矛盾,所以得到g[n]< g[n-1]。
也就是说,当f[n-1]< g[n-1],可以确定f[n-1]< f[n]和g[n]< g[n-1],反之则异。

可以列出:
当f[n-1]< g[n-1]时,
$f[n]=p\cdot g[n-1]+(1-p)\cdot g[n]$
$g[n]=q\cdot f[n-1]+(1-q)\cdot f[n]$
解方程=>
$f[n]=(p\cdot g[n-1]+(1-p)\cdot q\cdot f[n-1]) / (1-(1-p)\cdot (1-q))$
$g[n]=(q\cdot f[n-1]+(1-q)\cdot p\cdot g[n-1]) / (1-(1-p)\cdot (1-q))$
当f[n-1]> g[n-1]时,相似的,有
$f[n]=((1-p)\cdot g[n-1]+p\cdot (1-q)\cdot f[n-1]) / (1-(1-p)\cdot (1-q))$
$g[n]=((1-q)\cdot f[n-1]+q\cdot (1-p)\cdot g[n-1]) / (1-(1-p)\cdot (1-q))$

递推求解就可以辣~注意边界条件

这里有一个处理技巧,概率题里常用到:我们发现,当n足够大时,由于浮点数运算等等一些原因,答案会稳定在一个值,如这题,n=100时值就稳定了,固当n>100时,直接算到100输出就可以了。

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=101;
double p[2],q[2];
double f[maxn],g[maxn];

int main(){
int kase,n; scanf("%d",&kase);
while(kase--){
scanf("%d%lf%lf",&n,&p[0],&q[0]);
n=min(n,100);
f[0]=0; g[0]=1;
p[1]=1-p[0]; q[1]=1-q[0];
for(int i=1;i<=n;i++){
bool t=g[i-1]<f[i-1];
f[i]=(p[t]*g[i-1]+p[!t]*q[t]*f[i-1])/(1-p[!t]*q[!t]);
g[i]=(q[t]*f[i-1]+q[!t]*p[t]*g[i-1])/(1-p[!t]*q[!t]);
}
printf("%lf\n",f[n]);
}
return 0;
}