返回题解分享
讨论 / 题解分享/ 帖子详情

魔法羽毛 - 题解

数据范围1000,很可能解法就是n方级别的了。
然后理解一下题意:游戏开始,如果第一轮A赢,则需要第一次就抽中白羽,否则这一轮需要两个人都抽中黑羽,然后一个羽毛消失,进入下一轮。很明显是个dp(记忆化搜索)了。
注意一下如果某一轮黑羽的数量是1,则A要获胜必须直接抽中白羽。特判一下就好。
vector<vector<double>> st(1010,vector<double>(1010,-1));
double solve(int w,int b){
    double &v = st[w][b];
    if(v >= 0) return v;
    double dw = (double )w;
    double db = (double )b;

    double win = dw/(dw+db);
    if(b==1){
        return v = win;
    }else{
        double nxt = db/(dw+db)*(db-1)/(dw+db-1);
        v = win + nxt *( dw/(dw+db-2)*solve(w-1,b-2) + (db-2)/(dw+db-2)*solve(w,b-3));
    }
    return v;
}
void solve(){
    int W,B;
    cin>>W>>B;
    for(int i=1;i<=W;i++) st[i][0] = 1.0;
    for(int i=0;i<=B;i++) st[0][i] = 0.0;
    cout<<fixed<<setprecision(10)<<solve(W,B)<<endl;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!