[TopCoder SRM420 Div1 500pt RedIsGood]【数学期望】【动态规划】

【题意】

给你R张红牌,B张黑牌。

全翻过去。你每次可以选择翻开一张牌或者结束游戏。

翻开一张红牌你可以的1块钱,黑牌掉1块钱。

问假设你绝顶聪明,你得到的钱数是数学期望是多少?

【算法】

本来觉得红牌多就继续取,黑牌多不取了就是最优策略。

然后有个样例  11 12,期望居然>1。这才猛然发现可以通过见好就收的策略使得期望>0,于是就囧了。

解法是F[i][j]表示剩下i张红牌,j张黑牌,你绝顶聪明时的期望。

那么你怎么才叫聪明呢- -,当然是翻了以后,你继续聪明,得分的数学期望>0,那么就跑去翻,这样才叫聪明啊…

于是F[0][0]=0

F[i][j]=F[i-1][j]+1   (j=0)

F[i][j]=0                (i=0)

F[i][j]= max(  (F[i-1][j]+1)*(i/(i+j))  +  (F[i][j-1])*(j/(i+j))   ,   0   )

最后F[R][B]就是期望…

要用滚动数组优化一下。

【CODE】

 http://ideone.com/tfZ9a

加入对话

3条评论

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注