oldherd 是一名矿工。为了激励他工作,除了基础工资以外,老板还会将他采矿的一部分收益作为提成给予奖励。因此,oldherd 需要制定一个详细的计划,来确保他的总酬金(基础工资加上提成)具有最大化的期望。
形式化地来讲,在 天中,每一天 oldherd 都可以选择做矿工或者旷工。我们定义 为截止第 天结束时的挖矿收益。初始时,。如果在第 天选择采矿,将会使挖矿收益增加 ,即 。如果选择旷工,则挖矿收益不变,即 。
但是采矿是一项极具危险性的工作。在第 天时,有 的概率发生矿难。如果在第 天发生矿难,且在这一天 oldherd 选择了下矿,即便他拥有(鹿目)圆神的护佑,不会受伤。但在这一天结束时,过去累积的挖矿收益会全部清空,即 。由于不会受伤,他之后的每天依然可以选择去采矿。
老板毕竟是老板,他会等概率地选择 天中的 天时间,在这 天中他会派人来矿上监工。如果 oldherd 在老板派人来监工的任意一天中选择了旷工,oldherd 就会被开除,且被扣除全部酬金。
反之,如果 oldherd 旷工的每一天都没有被发现,他就可以顺利获得老板给出的基础工资 和第 天结束时挖矿收益的 ,即 作为总酬金。
现在一切都还没有发生,oldherd 预测了老板会来监工的天数 ,但不知道老板具体会哪天来监工。所谓富贵险中求,他想让你为他制定一个最优计划,提前决定好 天中的每一天是否采矿,并最大化总酬金的期望。
你需要对于所有的 ,输出最优方案下的期望总酬金 。