桌面上有R 张红牌和B 张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1 美元，黑牌则付出1 美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。
R,B ≤ 100000.
输入格式：
若干行,每行两个整数R,B
输出格式：
一个实数期望值.
样例输入：
68 7
样例输出
61.103
分析：这道题加深了我对期望+dp的理解.考虑dp,设f[i][j]表示还剩下i张红牌j张黑牌的期望值，这个时候如果停止翻牌，那么f[i][j] = 0,如果继续翻牌，就有i/i+j的概率翻到红牌，j/i+j的概率翻到黑牌，那么f[i][j] = (f[i-1][j] + 1) * i/(i + j) + (f[i][j-1] - 1) * j/(i + j).
这个时候我就有点疑惑了，为什么这个方程的期望值f[i-1][j],f[i][j-1]要乘上概率而noip2016d1t3那道题不需要呢？经过长时间的思索，我终于明白了，换教室那道题不用乘概率是因为那是两个不同的决策，它们并不在同一个决策里,而这一题要么不翻，要么翻，而实际上期望都在同一个决策里，所以有几率翻到红牌或者黑牌，所以要乘上概率.
一般期望题首先要考虑有没有公式，然后试试dp,dp的话一边直接用期望值表示状态.
数据过大，用了滚动数组.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; int r,b,last = ,now = ; const int maxn = 1e5+; double f[][maxn]; int main()
{
while (scanf("%d%d",&r,&b))
{
memset(f,,sizeof(f));
for (int i = ; i <= r; i++)
{
f[now][] = i;
for (int j = ; j <= b; j++)
f[now][j] = max(0.0,(f[last][j] + ) * i/(i + j) + (f[now][j-] - ) * j / (i + j));
swap(now,last);
}
printf("%.3lf\n",f[last][b]);
} return ;
}