JAG Spring Contest 2015

提交地址

Overview:

做 ASC 42 的 B 题的时候遇到的问题。。。ASC 42 的题目是:
初始有 m 元钱,目标是恰好拥有 n 元钱
每轮你可以压至多当前你所拥有的钱数进行赌博,p 的概率翻倍,q 的概率失去赌注。
至多进行 t 个回合,问最优策略下达到目标的概率。
(t <= 300, p < 50。)

YY 了一下结论,假设当前有 m 元钱,每次压 min(m, n-m) 就可以了。
加之题目限制很强,模拟 DP 一下就出来了。在 camp 群里遂问了一下 p >= 50 的情况下结论还成立吗。。
果然有完整版的题目。

ゆっくり読んでください ...