【概率dp】【BZOJ2318】Spoj4060 game with probability Problem
Description
有n个石子，A和B轮流做游戏，A先手，每次抛硬币，若正面朝上就拿走一枚石子，否则不作任何事。取到最后一颗石子的人胜利。AB都想取胜，A有p机率抛到想要的，B有q(p,q>=0.5)。求A获胜的概率。
Solution
设f[i]表示A为先手A赢的概率，g[i]为B为先手A赢的概率。
对于f[i]，显然从max(g[i],g[i-1])转移，g[i]类似，不过要从min转移。
那么有f[i]=p*g[i-1]+(1-p)*g[i],g[i-1]>g[i]
g[i]=q*f[i-1]+(1-q)*f[i],f[i-1]<f[i]
讨论一下发现，若f[i-1]>g[i]那么f[i-1]<f[i]一定成立，反之亦然。
于是化简上面的式子得到
f[i]=(p*g[i-1]+q*(1-p)*f[i-1])/(p+q-p*q);
g[i]=(q*f[i-1]+p*(1-q)*g[i-1])/(p+q-p*q);
易得到，当g[i-1]>f[i-1]时，AB都愿意取，否则都不愿意取，于是讨论一下就行了。
概率题有一个技巧，n很大之后变化往往不大，于是只用算到一个可以接受又不影响答案的值就可以了。
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1005;
double f[maxn],g[maxn],p,q;
int n,T;
int main(){
scanf("%d",&T);
f[0]=0,g[0]=1;
while(T--){
scanf("%d%lf%lf",&n,&p,&q);
n=min(n,1000);
for(int i=1;i<=n;i++){
if(g[i-1]<f[i-1]) p=1-p,q=1-q;
f[i]=(p*g[i-1]+q*(1-p)*f[i-1])/(p+q-p*q);
g[i]=(q*f[i-1]+p*(1-q)*g[i-1])/(p+q-p*q);
if(g[i-1]<f[i-1]) p=1-p,q=1-q;
}
printf("%.6lf\n",f[n]);
}
return 0;
}
2015年7月10日 07:45
说好的...."以后还是不做一题写一题了，一个专题的放在一个贴子里。"....窝还想看概率DP专题呢....