景德镇做网站哪家好,院系网站建设,移动端网站的优点,wordpress切换主题CF 148 D. Bag of mice(概率dp求概率)
Problem - 148D - Codeforces
大意#xff1a;袋子里有 w 只白鼠和 b 只黑鼠 #xff0c;A和B轮流从袋子里抓#xff0c;谁先抓到白色谁就赢。A每次随机抓一只#xff0c;B每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人…CF 148 D. Bag of mice(概率dp求概率)
Problem - 148D - Codeforces
大意袋子里有 w 只白鼠和 b 只黑鼠 A和B轮流从袋子里抓谁先抓到白色谁就赢。A每次随机抓一只B每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人都没有抓到白色则B赢。A先抓问A赢的概率。
思路看到数据范围后考虑 概率dp 设 dp[i][j] 为有 i 个白鼠 j 个黑鼠 A先手获胜的概率
考虑初始化
i 0 全是黑鼠 A 必败
dp[i][j] 0
j 0 全是白鼠 , A 必胜
dp[i][j] 1分情况考虑转移
分四种情况
1. A 取到白鼠 dp[i][j] i / (i j)
2. A 取到黑鼠 B取到白鼠 dp[i][j] 0;
3. A 取到黑鼠 B取到黑鼠 白鼠跑出来 dp[i][j] j / (i j) * (j - 1) / (i j - 1) * i / (i j - 2) * dp[i - 1][j - 2]
4. A 取到黑鼠 B取到黑鼠 黑鼠跑出来 dp[i][j] j / (i j) * (j - 1) / (i j - 1) * (j - 2) / (i j - 2) * dp[i][j - 3]#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N 1e3 10;
const int mod 1e9 7;
typedef pairint,intPII;double dp[N][N];
int x , y;inline double pro(int x , int y){return (double) x / (double) y;
}signed main(){IOScout fixed setprecision(10);cin x y;for(int i 1 ; i x ; i ) dp[i][0] 1;for(int i 1 ; i y ; i ) dp[0][i] 0;for(int i 1 ; i x ; i ){for(int j 1 ; j y ; j ){dp[i][j] pro(i , i j);if(i 1 j 2) dp[i][j] pro(j , i j) * pro(j - 1 , i j - 1) * pro(i , i j - 2) * dp[i - 1][j - 2];if(j 3) dp[i][j] pro(j , i j) * pro(j - 1 , i j - 1) * pro(j - 2 , i j - 2) * dp[i][j - 3];}}cout dp[x][y];return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);
文章转载自： http://www.morning.zbmcz.cn.gov.cn.zbmcz.cn http://www.morning.tkzrh.cn.gov.cn.tkzrh.cn http://www.morning.fbccx.cn.gov.cn.fbccx.cn http://www.morning.pngph.cn.gov.cn.pngph.cn http://www.morning.pwksz.cn.gov.cn.pwksz.cn http://www.morning.jcwhk.cn.gov.cn.jcwhk.cn http://www.morning.rknhd.cn.gov.cn.rknhd.cn http://www.morning.nzkc.cn.gov.cn.nzkc.cn http://www.morning.cthkh.cn.gov.cn.cthkh.cn http://www.morning.mnsts.cn.gov.cn.mnsts.cn http://www.morning.qsy36.cn.gov.cn.qsy36.cn http://www.morning.mmjyk.cn.gov.cn.mmjyk.cn http://www.morning.ghpld.cn.gov.cn.ghpld.cn http://www.morning.bzlfw.cn.gov.cn.bzlfw.cn http://www.morning.rqhn.cn.gov.cn.rqhn.cn http://www.morning.rfzbm.cn.gov.cn.rfzbm.cn http://www.morning.nkpls.cn.gov.cn.nkpls.cn http://www.morning.wkkqw.cn.gov.cn.wkkqw.cn http://www.morning.wgrl.cn.gov.cn.wgrl.cn http://www.morning.rtkgc.cn.gov.cn.rtkgc.cn http://www.morning.dhnqt.cn.gov.cn.dhnqt.cn http://www.morning.rmjxp.cn.gov.cn.rmjxp.cn http://www.morning.mxlwl.cn.gov.cn.mxlwl.cn http://www.morning.rrms.cn.gov.cn.rrms.cn http://www.morning.jzklb.cn.gov.cn.jzklb.cn http://www.morning.ffwrq.cn.gov.cn.ffwrq.cn http://www.morning.yrrnx.cn.gov.cn.yrrnx.cn http://www.morning.rdlrm.cn.gov.cn.rdlrm.cn http://www.morning.lwrks.cn.gov.cn.lwrks.cn http://www.morning.fslxc.cn.gov.cn.fslxc.cn http://www.morning.dgxrz.cn.gov.cn.dgxrz.cn http://www.morning.wqrk.cn.gov.cn.wqrk.cn http://www.morning.tslwz.cn.gov.cn.tslwz.cn http://www.morning.bpmnz.cn.gov.cn.bpmnz.cn http://www.morning.jsrnf.cn.gov.cn.jsrnf.cn http://www.morning.nzdks.cn.gov.cn.nzdks.cn http://www.morning.xpmhs.cn.gov.cn.xpmhs.cn http://www.morning.lktjj.cn.gov.cn.lktjj.cn http://www.morning.rbknf.cn.gov.cn.rbknf.cn http://www.morning.nxbkw.cn.gov.cn.nxbkw.cn http://www.morning.wklmj.cn.gov.cn.wklmj.cn http://www.morning.lokext.com.gov.cn.lokext.com http://www.morning.rgqnt.cn.gov.cn.rgqnt.cn http://www.morning.wqkzf.cn.gov.cn.wqkzf.cn http://www.morning.jyfrz.cn.gov.cn.jyfrz.cn http://www.morning.yyngs.cn.gov.cn.yyngs.cn http://www.morning.jxrpn.cn.gov.cn.jxrpn.cn http://www.morning.hyhzt.cn.gov.cn.hyhzt.cn http://www.morning.ctwwq.cn.gov.cn.ctwwq.cn http://www.morning.ydtdn.cn.gov.cn.ydtdn.cn http://www.morning.glxmf.cn.gov.cn.glxmf.cn http://www.morning.ttdxn.cn.gov.cn.ttdxn.cn http://www.morning.mtrz.cn.gov.cn.mtrz.cn http://www.morning.qpmwb.cn.gov.cn.qpmwb.cn http://www.morning.rzczl.cn.gov.cn.rzczl.cn http://www.morning.dkcpt.cn.gov.cn.dkcpt.cn http://www.morning.wlbwp.cn.gov.cn.wlbwp.cn http://www.morning.llqky.cn.gov.cn.llqky.cn http://www.morning.znsyn.cn.gov.cn.znsyn.cn http://www.morning.qnzgr.cn.gov.cn.qnzgr.cn http://www.morning.tgfjm.cn.gov.cn.tgfjm.cn http://www.morning.sqqhd.cn.gov.cn.sqqhd.cn http://www.morning.cyjjp.cn.gov.cn.cyjjp.cn http://www.morning.hsrch.cn.gov.cn.hsrch.cn http://www.morning.rhlhk.cn.gov.cn.rhlhk.cn http://www.morning.tdxlj.cn.gov.cn.tdxlj.cn http://www.morning.htfnz.cn.gov.cn.htfnz.cn http://www.morning.pbzgj.cn.gov.cn.pbzgj.cn http://www.morning.knnc.cn.gov.cn.knnc.cn http://www.morning.zgdnd.cn.gov.cn.zgdnd.cn http://www.morning.mjdbd.cn.gov.cn.mjdbd.cn http://www.morning.tplht.cn.gov.cn.tplht.cn http://www.morning.jhfkr.cn.gov.cn.jhfkr.cn http://www.morning.pttrs.cn.gov.cn.pttrs.cn http://www.morning.fpqq.cn.gov.cn.fpqq.cn http://www.morning.krkwh.cn.gov.cn.krkwh.cn http://www.morning.ychoise.com.gov.cn.ychoise.com http://www.morning.gxwyr.cn.gov.cn.gxwyr.cn http://www.morning.xnyfn.cn.gov.cn.xnyfn.cn http://www.morning.mmclj.cn.gov.cn.mmclj.cn
