也许更好的阅读体验
文章目录
- 数学期望
- 转移方程
- 经典例题
- SP1026FavoriteDice
- 涂格子/小孩和礼物
- 简单题
- 亚瑟王
- 抽卡
- 收集邮票
数学期望
符号
E=p∗v 其中E为期望,v为权值,p为概率
含义
期望表示多个可能事件的合理分配情况 (本人自己的理解,不喜勿喷)
汉语期望意思是指人们对某样东西的提前勾画出的一种标准,达到了这个标准就是达到了期望值(百度百科)
数学期望也可认为是进行某件事能得到的平均结果,或者理想代价
期望值也许和每个得到值都 不相等
举个例子
你去买彩票,每张彩票10元,中了奖可以得10000元,有30%的概率中奖
我们来算一下买一张彩票的期望利润
首先有30%的概率中奖,根据定义期望得到30%∗10000元
又有70%的概率不中奖,那么我们期望得到70%∗0元
我们每次买一张彩票100会花掉10元
所以有E=30%∗10000+70%∗0−10=290
我们可认为每买一张彩票赚了290元
但是实际上无论怎样,一张彩票都不会赚290元的。
转移方程
几种常见设转移方程数组的方法
- 设f[i]表示的是变成由i状态变成 最终 状态的期望
- 按照题意直接设
- 把选择的东西加入数组,如f[i][j]表示第i个物品选j个的期望或f[i][j]表示有i个A物品,j个B物品的期望
求转移方程
应优先考虑进行操作后当前状态会怎么样,而不是如何变成当前状态,即先考虑 逆向
如果逆向没有思路,则考虑 正向
经典例题
注:没有贴出代码,有些题目现在找不到了 (至少博主没有找到),也有博主自己想的题目 (很水),如博主有写代码则已放进标题的链接里,那些链接都是题解,不是原题链接
题目大意
一个n面的骰子,求期望掷几次能使得每一面都被掷到
解决方法
设f[i]表示已经掷到过i面,还 期望掷多少次骰子使每一面都被掷到
现在掷一次骰子,有两种情况
- 有ni的概率掷到已经掷到过的面,此时仍然还要掷f[i]次骰子
- 有nn−i的概率掷到没掷到过的面,此后就掷到过i+1个面了,还需掷f[i+1]次骰子
需要注意的是,无论是掷到以上哪种情况,都需要掷一次骰子
所以有
f[i]=nif[i]+nn−if[i+1]+1
将其化简
f[i]=f[i+1]+n−in
初值f[n]=0,答案为f[0]
应逆向循环
题目大意
有n个格子,每次等概率随机给一个格子染色,问涂m次后期望有多少格子被染色了
解决方法
设f[i]表示涂i次后期望有多少格子被染色了
现在进行第i次染色,仍然有两种情况
- 有nf[i−1]的概率涂到已经涂过的格子
- 有nn−f[i−1]的概率涂到没涂过的格子
需要注意的是,无论是以上哪种,都已经有f[i−1]个格子被染色了
所以有
f[i]=nf[i−1]⋅0+nn−f[i−1]⋅1+f[i−1]
将其化简
f[i]=nn−f[i−1]+f[i−1]=nn−1f[i−1]+1
此时该式就是一个等差数列套等比数列
于是我们可以求其通项公式,博主懒得求了写下大致过程
令k=nn−1
fn=kfn−1+1
fn+k−11=kfn−1+k−1k
fn+k−11=k(fn−1+k−11)
令gn=fn+k−11
则gn=kgn−1
怎么求gn就不用说了吧
fn=gn−k−11
fn也能求出来了
初值f[0]=0∣f[1]=1答案为f[m]
应正向循环
题目大意
桌面上有R张红牌和B张黑牌,随机打乱顺序后放在桌面上,开始一张一张地翻牌,翻到红牌得到1美元,黑牌则付出1美元。可以随时停止翻牌,在最优策略下平均能得到多少钱。
解决方法
设f[i][j]表示有i张红牌,j张黑牌的期望收益
考虑翻一张牌,还是有两种情况
- 有i+ji的概率翻到红牌,此后就只有i−1张红牌,j张黑牌
- 有i+jj的概率翻到黑牌,此后就只有i张红牌,j−1张黑牌
需要注意的是,不要忘了翻开的牌的贡献
翻开一张牌后,该颜色牌数目就少了一张
所以有
f[i][j]=i+ji(f[i−1][j]+1)+i+jj(f[i][j−1]−1)
由于是最优策略,所以咱是不可能赔钱的
f[i][j]=max(0,i+ji(f[i−1][j]+1)+i+jj(f[i][j−1]−1))
初值f[0][1]=0,f[1][0]=1,答案为f[R][B]
应正向循环
题目大意
给出n个技能,每个技能按输入顺序有p[i]的概率释放并造成d[i]的伤害。每轮游戏从前往后顺序查看每个技能,若技能发动过则跳过,没发动过则以p[i]的技能发动,即每个技能只能发动一次,若将一个技能发动,则进行下一轮游戏,没有成功发动或被跳过就查看下一个技能,一轮游戏可能每个技能都不发动,问r轮游戏一共能造成的伤害期望。
解决方法
因为有一个顺序查看的限制,没有后效性的状态是十分不好设的,因为不知道前面有几个技能发动了,若一个技能前面的技能在某轮发动了,则该技能本轮一定不能发动,若前面有些技能发动过,则它们都会被跳过
为了解决这种情况,我们设状态时试着强制限制技能发动(nr枚举情况),当然,设的状态仍然要满足 所有 情况都考虑在内
设f[i][j]表示对前i个技能进行了j轮游戏造成的 概率
若有前i个技能进行了j
则有j轮不会考虑第i+1个技能
即有r−j轮游戏选择了i之后的技能
此时考虑第i+1个技能的情况,分为两种
- 有p[i+1]r−j的概率i+1号技能从未发动
- 有1−p[i+1]r−j的概率i+1号技能发动过
需要注意的是,此时 已经 确定前i个技能进行并 只进行 了j轮游戏,其概率应该也计算在内
所以有
- f[i+1][j]+=1−p[i+1]r−jf[i][j]
- f[i+1][j+1]+=(1−p[i+1]r−j)f[i][j]
j+1要小于等于r
初值f[0][0]=1,答案在中途计算
应正向循环
计算了概率,别忘了求的是期望伤害,在求概率的时候顺便用概率乘以伤害
抽卡
题目大意
Morning_Glory最近迷上了抽卡,每次抽卡抽到6星卡的概率为p。抽卡活动进行n天,在第i天要花c[i]游戏币进行抽卡。求Morning_Glory抽得k张6星卡数时的期望游戏币花费。
解决方法
设f[i][j]表示第i天抽到j张6星卡的期望游戏币花费
在第i天进行抽卡,有两种情况
- 有p的概率抽到6星卡
- 有1−p的概率没抽到6星卡
需要注意的是无论是否翻到,都要花费
所以有
f[i][j]=p⋅f[i−1][j−1]+(1−p)⋅f[i−1][j]+c[i]
初值f[0][0]=1,f[0][1]=0,答案为f[n][k]
应正向循环
题目大意
有n种邮票,每天等概率的买一张邮票,第i天购买要花费i元,求收集n种邮票的期望花费
解决方法
先设f[i]表示买到i种邮票后,离买到n种邮票的期望还差天数
和最上面那题一样的处理方法
考虑当前买了i张邮票,再买一张邮票,有两种情况
- 有ni的概率买到重复的邮票,此时仍只买到i张邮票
- 有nn−i的概率买到没买过的邮票,此后就已买到i+1张邮票
需要注意的是,无论哪种情况,都过了一天
所以有
f[i]=nif[i]+nn−if[i+1]+1
将其化简
f[i]=f[i+1]+n−in
初值f[n]=0,答案为f[0]
应逆向循环
当然这只是期望天数,不是期望花费
设g[i]表示 拥有(不是买)i种邮票, 买到n种邮票的期望花费
考虑当前拥有了i张邮票,买一张邮票,有两种情况
- 有ni的概率买到重复的邮票,此时仍只拥有i种
- 有nn−i的概率买到没买过的邮票,此后就已拥有i+1张邮票
需要注意的是,无论哪种情况,都买了一张邮票
此时我们不知道每张邮票多少钱
但我们知道每张邮票和过了多少天有关
这次的注意写在前面,我们是认为有了i张邮票后才开始,所以第一天邮票价格为1元
为什么这么设?
我们不知道也不好处理出前面买了多少张邮票,再买到一张邮票要多少钱
但是我们知道第一天肯定是只要1元的,答案为g[0],中间的过程不重要,只需推出最终答案
我们借助初始状态的这条非常有用的性质于是就设出了这样的g
这样我们可以知道
- 若买到重复的邮票,我们知道,因为是设当前是第一天,所以原本希望买到的邮票的天数又往后推了一天,所以总价格要多f[i]元,还要加上自己的1元
- 若买到没买过的邮票,同理,因为后面的g[i+1]也是从第1天开始考虑的,所以原本希望买到的邮票数也往后推了一天,所以价格要多f[i+1]元,还要加上自己的1元
所以有
- g[i]+=ni(g[i]+f[i]+1)
- g[i]+=nn−i(g[i+1]+f[i+1]+1)
总写下来就是g[i]=ni(g[i]+f[i]+1)+nn−i(g[i+1]+f[i+1]+1)
将其化简得到
g[i]=n−iif[i]+g[i+1]+f[i+1]+n−in
初值g[n]=0,答案为g[0]
应逆向循环
如有哪里讲得不是很明白或是有错误,欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
如能得到推荐博主就更开心了
您的鼓励是博主的动力