首页 > 代码库 > codeforces-148D-Bag of mice-概率DP
codeforces-148D-Bag of mice-概率DP
dp[x][y]:现在有x个白老鼠,y个黑老鼠,公主赢的概率。
那么:
如果公主直接拿到白老鼠,概率为x/(x+y),公主赢。
如果公主拿到黑老鼠,概率为y/(x+y),那么公主如果想赢,龙必须拿到黑老鼠,概率为(y-1)/(x+y-1);
那么逃跑的老鼠为黑老鼠的概率为(y-2)/(x+y-2),为白老鼠的概率为(x)/(x+y-2);
那么dp[x][y]=x/(x+y)+y/(x+y) * (y-1)/(x+y-1) * ( (y-2)/(x+y-2) * dp[x][y-3] + (x)/(x+y-2) * dp[x-1][y-2] );
记忆化深搜也行,直接递推DP也行。
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stdlib.h> #include<vector> #include<cmath> #include<queue> #include<set> #include<stack> using namespace std; #define N 100010 #define LL long long #define INF 0xfffffff #define maxn 1100 double dp[maxn][maxn]; double dos(int x,int y) { if(x<0||y<0)return 0; if(x==0)return 0; if(y==0)return 1; if(dp[x][y]>-0.5)return dp[x][y]; double a,b; a=1.0*x; b=1.0*y; dp[x][y]=a/(a+b); if(x+y>=3) { dp[x][y]+=(b*(b-1)/((a+b)*(a+b-1)))* (dos(x-1,y-2)*a/(a+b-2)+dos(x,y-3)*(b-2)/(a+b-2)); } // cout<<x<<" "<<y<<" "<<dp[x][y]<<endl; return dp[x][y]; } int main() { int a,b; while(~scanf("%d%d",&a,&b)) { memset(dp,-1,sizeof(dp)); printf("%.10lf\n",dos(a,b)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。