学步园

题目链接：CF 148D. Bag of mice

挺不错的题！

题意：一个笼子里放着w个白鼠 ，b个黑鼠，然后开始princess先去任意随机的取一个老鼠，如果是白鼠则princess 赢 ，否则dragon开始取任意一个白鼠，如果是白鼠dragon赢，否则由于dragon 比较粗暴使得每次dragon取后都会有一个老鼠蹦出笼子，问princess 赢的概率

其实这个问题的重叠子问题很明显，因为如果当前是 （b,w） 然后两人都取后肯定变成了( b' , w' )  b' <= b && w' < w'

状态表示： dp[ n ] [ m ] 表示 有n个白鼠 m个黑鼠 princess 赢的概率

接下来就简单了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

const int maxn=2010;
double dp[maxn][maxn];

int main()
{
    for(int i=0;i<=1000;i++) dp[0][i]=0;
    for(int i=1;i<=1000;i++)
    for(int j=0;j<=1000;j++)
    {
        dp[i][j]=i*1.0/(i+j);
        if(j>=2){
           double tmp1=0,tmp2=0;
           tmp1=i*1.0/(i+j-2)*dp[i-1][j-2];
           if(j>=3) tmp2=(j-2)*1.0/(i+j-2)*dp[i][j-3];
           dp[i][j]+=j*1.0/(i+j)*(j-1)/(i+j-1)*(tmp1+tmp2);
        }
    }
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
        printf("%.12lf\n",dp[n][m]);
    return 0;
}