这道真的是好题,不卡精度,不卡细节,但是思考的方式很巧妙!
一开始大家跟我想的应该差不多,用f[i][j]表示有i只白老鼠,j只黑老鼠的胜率,然后跑DP,然后我就发现,这样怎么做?还有一种不胜不负的平手情况,这个是继承,还是不继承?如果f[w][b]继承了不胜不负的状态,而题意说的是如果两方都没有抓到白老鼠,算公主输,这样不就错了吗??
膜了网上大牛的题解,答案是:继承!
why?记住,f[i][j]表示的是当前胜的可能。首先当j=0的时候,公主必胜,这个继承没有问题;如果j>0,f会继承到前面胜利的情况,也会记录到不胜不负的情况,继承了胜利的情况没有问题,而不胜不负呢?终其原头,要么i=0,要么j=0,这两种情况,i=0整个全部都不会继承到,j=0公主必胜,继承没有问题。
#include<cstdio>
#include<cstring>
using namespace std;
double f[][];
int main()
{
int w,b;
while(scanf("%d%d",&w,&b)!=EOF)
{
memset(f,,sizeof(f));
for(int i=;i<=w;i++)f[i][]=;
for(int i=;i<=w;i++)
{
for(int j=;j<=b;j++)
{
double x=double(i),y=double(j);
f[i][j]+=x/(x+y);//公主直接抓到白老鼠
if(j>=)f[i][j]+=(y/(x+y)) * ((y-)/(x+y-)) * (x/(x+y-)) * f[i-][j-];//公主抓黑老鼠,龙也抓黑老鼠,跑了白老鼠
if(j>=)f[i][j]+=(y/(x+y)) * ((y-)/(x+y-)) * ((y-)/(x+y-)) * f[i][j-];//公主抓黑老鼠,龙也抓黑老鼠,跑了黑老鼠
//这两种情况公主没赢啊??可是她没输,如果最后她没有抓到白鼠,i=0初始就是0,如果j为0了,那公主也可以抓到白老鼠
}
}
printf("%.9lf\n",f[w][b]);
}
return ;
}