TopCoder SRM420 Div1 500pt RedIsGood（topcoder排名）

TopCoder SRM420 Div1 500pt RedIsGood（topcoder排名）

桌面上有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 #include #include #include #include using namespace std; int r,b,last = 0,now = 1; const int maxn = 1e5+10; double f[2][maxn]; int main() { while (scanf("%d%d",&r,&b)) { memset(f,0,sizeof(f)); for (int i = 1; i <= r; i++) { f[now][0] = i; for (int j = 1; j <= b; j++) f[now][j] = max(0.0,(f[last][j] + 1) * i/(i + j) + (f[now][j-1] - 1) * j / (i + j)); swap(now,last); } printf("%.3lf\n",f[last][b]); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。