BZOJ1419 Red is good

期望概率的dp。。。我怎么可能会。。。

令f[i][j]表示还有i张红牌，j张黑牌时的期望最大收益

于是有状态转移方程：f[i][j] = max(0, (1 + f[i - 1][j]) * i / (i + j) + (-1 + f[i][j - 1]) * j / (i + j))

意思就是说要么就是抽一张牌获得收益的期望概率，要么就是0

边界情况：i = 0, f[i][j] = 0; j = 0, f[i][j] = i

注意输出啊啊啊啊啊！！！！

"HINT

输出答案时,小数点后第六位后的全部去掉,不要四舍五入."坑货。。。。

/**************************************************************
    Problem: 1419
    User: rausen
    Language: C++
    Result: Accepted
    Time:2204 ms
    Memory:884 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
 
using namespace std;
typedef double lf;
const int N = 5010;
 
int n, m, w;
lf f[2][N];
 
int main() {
  int i, j;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; ++i, w ^= 1) {
    f[w][0] = i;
    for (j = 1; j <= m; ++j)
      f[w][j] = max((lf) 0, i / lf (i + j) * (f[!w][j] + 1) + j / lf (i + j) * (f[w][j - 1] - 1));      
  }
  printf("%.6lf
", f[!w][m] - 5e-7);
  return 0;
}