概率DP

http://codeforces.com/problemset/problem/148/D

#include<cstdio>
#include<string.h>
using namespace std;
#define maxn 1005
double dp[maxn][maxn];
int main()
{
        int w,b;
        scanf("%d%d",&w,&b);
        for(int i=0;i<=b;i++)
        dp[0][i]=0.0;
        for(int j=1;j<=w;j++)
        dp[j][0]=1.0;
        for(int i=1;i<=w;i++)
        {
            for(int j=1;j<=b;j++)
            {
                dp[i][j]=(double)(i)/(j+i);
                if(j>=3) dp[i][j]+=1.0*j/(i+j)*1.0*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3];
                if(j>=2) dp[i][j]+=1.0*j/(i+j)*1.0*(j-1)/(i+j-1)*(i)/(i+j-2)*dp[i-1][j-2];
            }
        }
        printf("%.9f",dp[w][b]);
}

递归超时版本

#include<cstdio>
#include<string.h>
using namespace std;
double probability(double m,double n)
{
    if(m<=0) return 0;
    if(n<=0) return 1.0;
    double val=n/(m+n)*(n-1)/(m+n-1);
    return m/(m+n)+val*m/(m+n-2)*probability(m-1,n-2)+val*(n-2)/(m+n-2)*probability(m,n-3);
}
int main()
{
        int m,n;
        double dm,dn;
        scanf("%d%d",&m,&n);
        dm=m+0.0,dn=n+0.0;
        printf("%.9f",probability(dm,dn));
        //printf("%d\n",INF);
}