[中译] ProjectEuler 470 Super Ramvok

楼主: tml (流刑人形)   2014-05-06 04:52:15
Super Ramvok
http://projecteuler.net/problem=470
一场Ramvok游戏的规则如下:
令t表示一场游戏的总回合数。如果t=0则游戏立即终止。否则,每个回合玩家都能掷一颗
骰子。若目前回合数i<t,则玩家可以选择得到等同当前骰子点数的奖金,或是放弃这回
合的结果,在下个回合重新尝试一次。但如果i=t则无法放弃,直接得到最后一次骰出的
点数的奖金。在游戏开始之前,玩家可以自行选择t值,并先支付ct的赌金,其中c是一个
常数。如果c=0则即使选择t为无限大也不需支付任何赌金。令d为一场游戏所使用的公正
骰子的面数,则R(d,c)代表在给定d和c的情况下,使用最佳策略时,一场游戏的净利
(奖金减去赌金)的期望值。例如R(4,0.2) = 2.65。并假设玩家有足够的资金能够付出
任意赌金。
现在,我们更进一步考虑一场超级Ramvok游戏规则如下:
一场超级Ramvok中,我们会重复执行一般的Ramvok,并加上一些附加条件。在每场Ramvok
之后,都会改变一次骰子。改变的方法如下:先掷一次骰子,如果骰出的结果是数字,则
将其换成空白。反之,如果是已经空白,则回复成原本的数字。再用这个改变过的骰子执
行下一次的游戏。(游戏进行中时,将反复掷骰直到数字出现为止。)玩家自始至终都能
得知哪些数字是空白、哪些不是。一场超级Ramvok会在骰子的每一面都是空白时才结束。
令S(d,c)为给定d和c时,在最佳策略下,玩家在一场超级Ramvok中所能获得的净利的期
望值。在一开始游戏时,d面骰的每一面都是有数字的。举例而言,S(6,1) = 208.3。
令F(n) = ΣΣS(d,c)对4≦d≦n以及0≦c≦n的双重和。
请求出F(20),并四舍五入至整数位。
楼主: tml (流刑人形)   2014-05-06 09:08:00
Ramvok是这题的自创字,其实是Markov的重排…不知道算不算提示
作者: LPH66 (-6.2598534e+18f)   2014-05-06 23:50:00
这 Markov 很讨厌啊 QAQ 它是个 d 维超立方体的图理论上应该离开某个距离的点的值会有共同性但一下子找不出来(因为这是一个很显然的对称性...但还想不到要怎么利用)

Links booklink

Contact Us: admin [ a t ] ucptt.com