BZOJ2318:Spoj4060 game with probability Problem 期望dp

思路:

令还剩\(i\)个石子时Alice先手Alice的胜率为\(f_i\),Bob先手Alice的胜率为\(g_i\).我们发现当\(f_{i-1}>g_{i-1}\)时,双方都想不取(想想为什么).否则双方都想取.

然后我们分别算一下Alice和Bob先手时两个人想取(不想取)最终取得的概率.

这样就很容易进行递推了.

值得一提的是,递推是\(O(n)\)的.然而\(n\)太大怎么办?

打表发现随着\(n\)的增大,胜率越来越接近于0.5.因此\(n>1000\)时直接输出\(0.500000\)即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    int T;cin>>T;
    int n;f2 p,q;
    while(T--){
        cin>>n>>p>>q;if(n>1000)n=1000;
        f2 want_1fir_1=p/(1-(1-p)*(1-q)),want_1fir_2=(1-p)*q/(1-(1-p)*(1-q));
        f2 want_2fir_1=(1-q)*p/(1-(1-p)*(1-q)),want_2fir_2=q/(1-(1-p)*(1-q));
        p=1-p,q=1-q;
        f2 nwant_1fir_1=p/(1-(1-p)*(1-q)),nwant_1fir_2=(1-p)*q/(1-(1-p)*(1-q));
        f2 nwant_2fir_1=(1-q)*p/(1-(1-p)*(1-q)),nwant_2fir_2=q/(1-(1-p)*(1-q));
        f2 win_1fir=0,win_2fir=1,win_1,win_2;
        for(int i=1;i<=n;++i){
            if(win_1fir>win_2fir){
                win_1=nwant_1fir_1*win_2fir+nwant_1fir_2*win_1fir;
                win_2=nwant_2fir_2*win_1fir+nwant_2fir_1*win_2fir;
                win_1fir=win_1,win_2fir=win_2;
            }
            else{
                win_1=want_1fir_1*win_2fir+want_1fir_2*win_1fir;
                win_2=want_2fir_2*win_1fir+want_2fir_1*win_2fir;
                win_1fir=win_1,win_2fir=win_2;
            }
        }printf("%.6lf\n",win_1fir);
    }
    return 0;
}