HBC20263[SCOI2008]奖励关题解

三分之二給你 算法基础篇 61 0
想要检验自己的编程水平?来试试全网最全C++题库,让您在挑战中不断进步。
你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关,在这个奖励关里,系统将依次随机抛出k次宝物, 每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃), 宝物一共有n种,系统每次抛出这n种宝物的概率都相同且相互独立,也就是说,即使前k-1次系统都抛出宝物1( 这种情况是有可能出现的,尽管概率非常小),第k次抛出各个宝物的概率依然均为1/n。

你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物, 每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。   宝物一共有n种,系统每次抛出这n种宝物的概率都相同且相互独立。也就是说,即使前k-1次系统都抛出宝物1( 这种情况是有可能出现的,尽管概率非常小),第k次抛出各个宝物的概率依然均为1/n。  获取第i种宝物将得到Pi 分,但并不是每种宝物都是可以随意获取的。第i种宝物有一个前提宝物集合Si。 只有当Si中所有宝物都至少吃过 一次,才能吃第i种宝物(如果系统抛出了一个目前不能吃的宝物,相当于白白的损失了一次机会)。 注意,Pi可 以是负数,但如果它是很多高分宝物的前提,损失短期利益而吃掉这个负分宝物将获得更大的长期利益。 假设你采取最优策略,平均情况你一共能在奖励关得到多少分值?

HBC20263[SCOI2008]奖励关题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
不断学习,不断挑战,才能在编程领域中脱颖而出!全网最全C++题库,助您成为编程高手!

标签: HBC20263[SCOI2008]奖励关题解