数据范围1000,很可能解法就是n方级别的了。
然后理解一下题意:游戏开始,如果第一轮A赢,则需要第一次就抽中白羽,否则这一轮需要两个人都抽中黑羽,然后一个羽毛消失,进入下一轮。很明显是个dp(记忆化搜索)了。
注意一下如果某一轮黑羽的数量是1,则A要获胜必须直接抽中白羽。特判一下就好。
然后理解一下题意:游戏开始,如果第一轮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 阅读



