[TopCoder9915]RedIsGood(动态规划,期望概率)

发布于 2018-04-05  149 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[TopCoder9915]RedIsGood(动态规划,期望概率)

Description

You have a deck that contains R red and B black cards.
You are playing the following game: You shuffle the deck, and then begin dealing the cards one by one. For each red card you flip you get a dollar, and for each black card you flip you have to pay a dollar. At any moment (including the beginning of the game) you are allowed to stop and keep the money you have.
Write a method that will take the ints R and B, and return the expected amount you will gain if you play this game optimally.

Tag

动态规划,期望概率

题目大意

给出n张红牌和m张黑牌。现在把它们随机排列。翻到一张红牌获得1的收益,翻到一张黑牌会有1的损失。求随机情况下的最大收益

解决思路

由于是随机的,我们知道的信息只有当前已经翻了多少张红牌,多少张黑牌以及总共的两种颜色分别的牌数。那么,接下来或出现的牌的颜色我们是知道概率的,那么设\(F[i][j]\)表示还剩下i张红牌,j张黑牌,最大期望收益。根据概率有转移方程
\[F[i][j]=max(0,\frac{i}{i+j}*(F[i-1][j]+1)+\frac{j}{i+j}*(F[i][j-1]-1)\]
注意滚动。

代码

非滚动版本

滚动版本

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[TopCoder9915]RedIsGood(动态规划,期望概率)


HNCJ OIer