1 条题解
-
0
数据范围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; }
信息
- ID
- 218
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 7
- 已通过
- 3
- 上传者