| 
最適に選んだときの期待値は、残っている Red, Black の数が決まると定まる。
（ f(5, 1) の手計算でなかなか数が合わず苦労..）
漸化式は
f(r, b) = 0 (r=0)
= r (b=0)
= max(0, ( r * (1 + f(r-1, b)) + b (-1 + f(r, b-1)) ) / (r+b)) (else)
で、いつもならメモ化再帰を使うところだが、double [5001][5001] は 64MB に収まらないと気づいて、
ループDP＋メモリ使い回しを用いて double [5001] x 2 で済むようにした。
あと前 CatchTheMice で double だと微妙な誤差で通らなくて long double だと通ったトラウマ？があるので、誤差が 1e-9 までとかの場合は念のため long double を使うようになったでござる。
class RedIsGood { public: double getProfit(int R, int B) { vector<long double> dp(R+1); vector<long double> ndp(R+1); REP(r, R+1) dp[r]=r; for(int b=1;b<=B;b++) { ndp[0]=0.0; for(int r=1;r<=R;r++) { long double v = (r*(1+ndp[r-1]) + b*(-1+dp[r]))/(r+b); ndp[r] = max(v, 0.0l); } //cout<<ndp<<endl; dp=ndp; } return dp[R]; }
