下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 买彩票

买彩票.doc

买彩票

faint
2018-09-06 0人阅读 举报 0 0 暂无简介

简介:本文档为《买彩票doc》,可适用于高中教育领域

买彩票(ticktexe)电视里面正放着“抽百万大奖赢幸福生活”的宣传广告bird看后也想去试试手气当然作为经济学院的高材生他可不屑只是单纯的去碰运气。经过他的一番分析发现商家在彩票里面做了手脚使得每个抽奖点的中奖概率不是完全一样的而且随着时间的变化而变化不过这种变化是有规律的。对于第I个抽奖点最开始的中奖概率是百万分之Pi以后每抽一张彩票后都要重新排队花费的时间是T分钟每抽一次减少的概率为Di。由于可怜的bird还有一大堆的作业没做他只能抽出H个小时去买彩票。由于抽奖地点都在一路公共汽车的线路上所以怕麻烦的bird决定按车站顺序抽奖当然bird可以从任意一站开始抽奖对于经过的抽奖点可以买彩票也可以不买。假设从第I个抽奖点到第I个抽奖点需要做Ci分钟的汽车。Bird希望能在有限的H个小时内获得最好的运气即抽奖的概率和最大。输入:第一行为一个整数n表示抽奖点的个数<=n<=第二行是两个整数H和T<=H<=<=T<=。接下来的n行每行个整数分别是PiDiCi(Cn=)。<=Pi<=Di<=Pi<=Ci<=。输出:一个整数抽奖概率和的最大值。样例数据inputtxtoutput样例说明:首先bird从号开始抽奖花费分钟得到概率然后坐车到号花费分钟再花分钟得到概率概率和是花费分钟。分析:此题最初可能想到用搜索不过如果仔细分析题目会发现其实用贪心就可以解了。虽然中奖的概率会不断变化但概率只和在该抽奖地点的抽奖次数有关和抽奖的总次数以及时间无关。所以我们可以枚举起始S和终点T的抽奖地点则在路上花费的时间可以求出那么在这个范围内的抽奖可以看作bird能瞬间转移那么我们只需将此范围内的抽奖概率排序取前若干个使得花费的时间不超过时限。很容易证明这种方法是最优的。此题的贪心关键是要先确定一个范围然后针对具体的范围贪心。贪心法的隐秘性还是比较强的。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/1

买彩票

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利