php 做网站xml地图,品牌创意网站建设,免费高清logo,怎么创建图片链接https://www.luogu.com.cn/problem/CF148D
思路#xff1a;
概率dp#xff0c;设f[a][b]为白鼠为a个#xff0c;黑鼠为b个时#xff0c;赢的期望。
f[i][0]1;
1.当先手取到白鼠时 a/(ab);
2.当先手未取到白鼠#xff0c;先手要向赢#xff0c;后手也不能取到白鼠
概率dp设f[a][b]为白鼠为a个黑鼠为b个时赢的期望。
f[i][0]1;
1.当先手取到白鼠时 a/(ab);
2.当先手未取到白鼠先手要向赢后手也不能取到白鼠跑掉的那一只随意
2.1 b/(ab)*(b-1)/(ab-1)*a/(ab-2);
2.2 b/(ab)*(b-1)/(ab-1)*(b-2)/(ab-2);
注意数据范围
代码
#includebits/stdc.h using namespace std; #define LL long long const int N1e5100; const int MAX1e9; double f[1100][1100]; int w,k; int main(){ cinwk; for(int i1;iw;i) f[i][0]1; for(int a1;aw;a) for(int b1;bk;b){ f[a][b]1.0*a/(ab); if(a1b2) f[a][b]1.0*b/(ab)*(b-1)/(ab-1)*a/(ab-2)*f[a-1][b-2]; if(b3) f[a][b]1.0*b/(ab)*(b-1)/(ab-1)*(b-2)/(ab-2)*f[a][b-3]; } printf(%.9lf\n,f[w][k]); return 0; }
