题解 | #Monster Killer# #概率期望#

Monster Killer

https://ac.nowcoder.com/acm/contest/43084/A

牛客43084A - Monster Killer

题意

n(n103)n(n\leq 10^3) 个怪物,每种怪物的抵御力为 aia_i

初始时,主人公的战斗力为 00,主人公需要按顺序击败这些怪物

在某次战斗中,假设主人公的战斗力为 mm,那么有如下情况:

  • m=aim=a_i,他击败了当前怪物
  • m>aim>a_i,他击败了当前怪物,并且有 pip_i 的概率他的战斗力变为 m1m-1
  • m<aim<a_i,他无法击败当前怪物,并且有 pip_i 的概率他的战斗力变为 m+1m+1

给出aia_ipip_i,问:要把所有怪物都击败,所需要的战斗次数的期望

思路1(倒推)

dp[i][j]dp[i][j] 代表第 ii 轮战斗,主人公有 jj 的战斗力。从当前情况开始,一直到击败所有怪物的期望。

dp[i][j]={dp[i+1][j1]×pi+dp[i+1][j]×(1pi),j>aidp[i+1][j],j=aidp[ai][j]+(aijpi),j<aidp[i][j] = \begin{cases} dp[i+1][j-1]\times p_i + dp[i+1][j]\times (1-p_i) &,j>a_i \\ dp[i+1][j] &,j=a_i \\ dp[a_i][j]+(\frac{a_i-j}{p_i}) &,j<a_i \end{cases}

思路2(正推)

  • f[i][j]f[i][j] 代表:第 ii 轮战斗,主人公有 jj 的战斗力。出现这种状态的概率
  • g[i][j]g[i][j] 代表:第 ii 轮战斗,主人公有 jj 的战斗力。从起点到该状态的操作次数的期望

转移注意事项

转移时,先转移 ff,等待 ff 完全转移结束后,再转移 gg

具体实现: 设 s1,s2,s3s_1,s_2,s_3 为之前的状态,p1,p2,p3p_1,p_2,p_3 为之前的状态对应的概率,e1,e2,e3e_1,e_2,e_3 为之前的状态对应的期望,q1,q2,q3q_1,q_2,q_3 为之前的状态能转移到当前状态的概率。 ss 为当前状态,pp 为当前的状态对应的概率,ee 为当前的状态对应的期望。

{s1(p1,e1,q1)s2(p2,e2,q2)s3(p3,e3,q3)=s(p=p1q1+p2q2+p3q3+,e=e1p1q1+e2p2q2+e3p3q3+p1q1+p2q2+p3q3+)\begin{cases} s_1(p_1,e_1,q_1) \\ s_2(p_2,e_2,q_2) \\ s_3(p_3,e_3,q_3) \\ \dots \end{cases}=s(p=p_1\cdot q_1+p_2\cdot q_2+p_3\cdot q_3+\dots,e=\frac{e_1\cdot p_1\cdot q_1+e_2\cdot p_2\cdot q_2+e_3\cdot p_3\cdot q_3+\dots}{p_1\cdot q_1+p_2\cdot q_2+p_3\cdot q_3+\dots})
概率、期望 文章被收录于专栏

概率期望、概率DP、期望DP

全部评论

相关推荐

07-23 14:04
东北大学 C++
既然这样,为什么不点击就送呢
牛马88号:因为你合适。但有很多笔试就挂了、通过了再排序的
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
07-02 10:39
门头沟学院 Java
Steven267:说点真实的,都要秋招了,还没有实习,早干嘛去了,本来学历就差,现在知道急了,而且你这个简历完全可以写成一页,劣势太大了,建议转测试
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-23 14:22
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务