1050 - Marbles PDF (English) Statistics ForumTime Limit: 2 second(s) Memory Limit: 32 MBYour friend Jim has challenged you to a game. He has a bag containing red and blue marbles. There will be an odd number of marbles in the bag, and you go first. On your turn, you reach into the bag and remove a random marble from the bag; each marble may be selected with equal probability. After your turn is over, Jim will reach into the bag and remove a blue marble; if there is no blue marble for Jim to remove, then he wins. If the final marble removed from the bag is blue (by you or Jim), you will win. Otherwise, Jim wins.
Given the number of red and blue marbles in the bag, determine the probability that you win the game.
InputInput starts with an integer T (≤ 10000), denoting the number of test cases.
Each case begins with two integers R and B denoting the number of red and blue marbles respectively. You can assume that 0 ≤ R, B ≤ 500 and R+B is odd.
OutputFor each case of input you have to print the case number and your winning probability. Errors less than 10-6 will be ignored.
Sample InputOutput for Sample Input51 22 32 511 64 11Case 1: 0.3333333333Case 2: 0.13333333Case 3: 0.2285714286Case 4: 0Case 5: 0.1218337218
解题思路: 以dp[R][B]作为状态方程，通过观察发现，但R>=B时，dp[R][B]肯定是为0的
当R<B时 我们可以发现dp[R][B] = R/(R+b)*dp[R-1][B-1] + B/(R+B)*dp[R][B-2];
根据这两个状态预处理好dp方程就可以了；
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; double dp[600][600]; void init(){ for(int i=1;i<510;i++) dp[0][i] = 1; for(int i=1;i<510;i++){ for(int j=i+1;j<510;j++){ dp[i][j] = (double)i*1.0/(i+j)*dp[i-1][j-1] + (double)j*1.0/(i+j)*dp[i][j-2]; } } return ; } int main(){ init(); int T,r,b; scanf("%d",&T); for(int t=1;t<=T;t++){ scanf("%d%d",&r,&b); printf("Case %d: %.6lf\n",t,dp[r][b]); } }
转载于:https://www.cnblogs.com/yuanshixingdan/p/5565609.html
相关资源：JAVA上百实例源码以及开源项目