Light OJ 1050 - Marbles（概率DP）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const int INF = 1e9+7;
const int MAXN = 555;
double dp[MAXN][MAXN];

double DFS(int R,int B)
{
    if(dp[R][B] != -1)
        return dp[R][B];
    if(R >= B || B == 0)
        return dp[R][B] = 0;
    if(R == 0)
        return dp[R][B] = 1;
    double k = 1.0/(R + B);
    if( (R+B)%2 )
        dp[R][B] =  1.0*R*k*DFS(R-1,B) + 1.0*B*k*DFS(R, B-1);
    else
        dp[R][B] = DFS(R, B-1);

    return dp[R][B];
}

int main()
{
    int T, cas = 1, n, R, B;
    for(int i=0; i<=500; i++)
    for(int j=0; j<=500; j++)
    dp[i][j] = dp[i][j] = -1;

    scanf("%d", &T);
    while(T --)
    {
        scanf("%d %d", &R, &B);

        printf("Case %d: %.9lf\n",cas ++, DFS(R, B) );
    }

    return 0;
}