期望DP

2019/7/22 20:06:55 人评论 次浏览 分类:学习教程

也许更好的阅读体验

文章目录

  • 数学期望
    • 符号
    • 含义
  • 转移方程
  • 经典例题
    • SP1026FavoriteDice
    • 涂格子/小孩和礼物
    • 简单题
    • 亚瑟王
    • 抽卡
    • 收集邮票


数学期望

符号

E=pvE=p*v 其中EE为期望,vv为权值,pp为概率

含义

期望表示多个可能事件的合理分配情况 (本人自己的理解,不喜勿喷)
汉语期望意思是指人们对某样东西的提前勾画出的一种标准,达到了这个标准就是达到了期望值(百度百科)
数学期望也可认为是进行某件事能得到的平均结果,或者理想代价
期望值也许和每个得到值都 不相等
举个例子
你去买彩票,每张彩票1010元,中了奖可以得1000010000元,有30%30\%的概率中奖
我们来算一下买一张彩票的期望利润
首先有30%30\%的概率中奖,根据定义期望得到30%1000030\%*10000
又有70%70\%的概率不中奖,那么我们期望得到70%070\%*0
我们每次买一张彩票100100%会花掉1010
所以有E=30%10000+70%010=290E=30\%*10000+70\%*0-10=290
我们可认为每买一张彩票赚了290290
但是实际上无论怎样,一张彩票都不会赚290290元的。


转移方程

几种常见设转移方程数组的方法

  1. f[i]f[i]表示的是变成由ii状态变成 最终 状态的期望
  2. 按照题意直接设
  3. 把选择的东西加入数组,如f[i][j]f[i][j]表示第ii个物品选jj个的期望或f[i][j]f[i][j]表示有iiAA物品,jjBB物品的期望

求转移方程
应优先考虑进行操作后当前状态会怎么样,而不是如何变成当前状态,即先考虑 逆向
如果逆向没有思路,则考虑 正向


经典例题

注:没有贴出代码,有些题目现在找不到了 (至少博主没有找到),也有博主自己想的题目 (很水),如博主有写代码则已放进标题的链接里,那些链接都是题解,不是原题链接

SP1026FavoriteDice

题目大意

一个nn面的骰子,求期望掷几次能使得每一面都被掷到

解决方法

f[i]f[i]表示已经掷到过ii面, 期望掷多少次骰子使每一面都被掷到
现在掷一次骰子,有两种情况

  1. in\frac{i}{n}的概率掷到已经掷到过的面,此时仍然还要掷f[i]f[i]次骰子
  2. nin\frac{n-i}{n}的概率掷到没掷到过的面,此后就掷到过i+1i+1个面了,还需掷f[i+1]f[i+1]次骰子

需要注意的是,无论是掷到以上哪种情况,都需要掷一次骰子
所以有
f[i]=inf[i]+ninf[i+1]+1f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1
将其化简
f[i]=f[i+1]+nnif[i]=f[i+1]+\frac{n}{n-i}

初值f[n]=0f[n]=0,答案为f[0]f[0]
应逆向循环


涂格子/小孩和礼物

题目大意

nn个格子,每次等概率随机给一个格子染色,问涂mm次后期望有多少格子被染色了

解决方法

f[i]f[i]表示涂ii次后期望有多少格子被染色了
现在进行第ii次染色,仍然有两种情况

  1. f[i1]n\frac{f[i-1]}{n}的概率涂到已经涂过的格子
  2. nf[i1]n\frac{n-f[i-1]}{n}的概率涂到没涂过的格子

需要注意的是,无论是以上哪种,都已经有f[i1]f[i-1]个格子被染色了
所以有
f[i]=f[i1]n0+nf[i1]n1+f[i1]f[i]=\frac{f[i-1]}{n}·0+\frac{n-f[i-1]}{n}·1+f[i-1]
将其化简
f[i]=nf[i1]n+f[i1]=n1nf[i1]+1f[i]=\frac{n-f[i-1]}{n}+f[i-1]=\frac{n-1}{n}f[i-1]+1
此时该式就是一个等差数列套等比数列
于是我们可以求其通项公式,博主懒得求了写下大致过程

k=n1nk=\frac{n-1}{n}
fn=kfn1+1f_n=kf_{n-1}+1
fn+1k1=kfn1+kk1f_n+\frac{1}{k-1}=kf_{n-1}+\frac{k}{k-1}
fn+1k1=k(fn1+1k1)f_n+\frac{1}{k-1}=k(f_{n-1}+\frac{1}{k-1})
gn=fn+1k1g_n=f_n+\frac{1}{k-1}
gn=kgn1g_n=kg_{n-1}
怎么求gng_n就不用说了吧
fn=gn1k1f_n=g_n-\frac{1}{k-1}
fnf_n也能求出来了

初值f[0]=0f[1]=1f[0]=0|f[1]=1答案为f[m]f[m]
应正向循环


简单题

题目大意

桌面上有R张红牌和B张黑牌,随机打乱顺序后放在桌面上,开始一张一张地翻牌,翻到红牌得到1美元,黑牌则付出1美元。可以随时停止翻牌,在最优策略下平均能得到多少钱。

解决方法

f[i][j]f[i][j]表示有ii张红牌,jj张黑牌的期望收益
考虑翻一张牌,还是有两种情况

  1. ii+j\frac{i}{i+j}的概率翻到红牌,此后就只有i1i-1张红牌,jj张黑牌
  2. ji+j\frac{j}{i+j}的概率翻到黑牌,此后就只有ii张红牌,j1j-1张黑牌

需要注意的是,不要忘了翻开的牌的贡献
翻开一张牌后,该颜色牌数目就少了一张

所以有
f[i][j]=ii+j(f[i1][j]+1)+ji+j(f[i][j1]1)f[i][j]=\frac{i}{i+j}(f[i-1][j]+1)+\frac{j}{i+j}(f[i][j-1]-1)
由于是最优策略,所以咱是不可能赔钱的
f[i][j]=max(0,ii+j(f[i1][j]+1)+ji+j(f[i][j1]1))f[i][j]=max(0,\frac{i}{i+j}(f[i-1][j]+1)+\frac{j}{i+j}(f[i][j-1]-1))

初值f[0][1]=0,f[1][0]=1f[0][1]=0,f[1][0]=1,答案为f[R][B]f[R][B]
应正向循环


亚瑟王

题目大意

给出nn个技能,每个技能按输入顺序有p[i]p[i]的概率释放并造成d[i]d[i]的伤害。每轮游戏从前往后顺序查看每个技能,若技能发动过则跳过,没发动过则以p[i]p[i]的技能发动,即每个技能只能发动一次,若将一个技能发动,则进行下一轮游戏,没有成功发动或被跳过就查看下一个技能,一轮游戏可能每个技能都不发动,问rr轮游戏一共能造成的伤害期望。

解决方法

因为有一个顺序查看的限制,没有后效性的状态是十分不好设的,因为不知道前面有几个技能发动了,若一个技能前面的技能在某轮发动了,则该技能本轮一定不能发动,若前面有些技能发动过,则它们都会被跳过
为了解决这种情况,我们设状态时试着强制限制技能发动(nrnr枚举情况),当然,设的状态仍然要满足 所有 情况都考虑在内
f[i][j]f[i][j]表示对前ii个技能进行了jj轮游戏造成的 概率
若有前ii个技能进行了jj
则有jj轮不会考虑第i+1i+1个技能
即有rjr-j轮游戏选择了ii之后的技能
此时考虑第i+1i+1个技能的情况,分为两种

  1. p[i+1]rjp[i+1]^{r-j}的概率i+1i+1号技能从未发动
  2. 1p[i+1]rj1-p[i+1]^{r-j}的概率i+1i+1号技能发动过

需要注意的是,此时 已经 确定前ii个技能进行并 只进行jj轮游戏,其概率应该也计算在内
所以有

  1. f[i+1][j]+=1p[i+1]rjf[i][j]f[i+1][j]+=1-p[i+1]^{r-j}f[i][j]
  2. f[i+1][j+1]+=(1p[i+1]rj)f[i][j]f[i+1][j+1]+=(1-p[i+1]^{r-j})f[i][j]

j+1j+1要小于等于rr

初值f[0][0]=1f[0][0]=1,答案在中途计算
应正向循环

计算了概率,别忘了求的是期望伤害,在求概率的时候顺便用概率乘以伤害


抽卡

题目大意

Morning_Glory\mathcal{Morning\_Glory}最近迷上了抽卡,每次抽卡抽到66星卡的概率为pp。抽卡活动进行nn天,在第ii天要花c[i]c[i]游戏币进行抽卡。求Morning_Glory\mathcal{Morning\_Glory}抽得kk66星卡数时的期望游戏币花费。

解决方法

f[i][j]f[i][j]表示第ii天抽到jj66星卡的期望游戏币花费
在第ii天进行抽卡,有两种情况

  1. pp的概率抽到66星卡
  2. 1p1-p的概率没抽到66星卡

需要注意的是无论是否翻到,都要花费
所以有
f[i][j]=pf[i1][j1]+(1p)f[i1][j]+c[i]f[i][j]=p·f[i-1][j-1]+(1-p)·f[i-1][j]+c[i]

初值f[0][0]=1,f[0][1]=0f[0][0]=1,f[0][1]=0,答案为f[n][k]f[n][k]
应正向循环


收集邮票

题目大意

nn种邮票,每天等概率的买一张邮票,第ii天购买要花费ii元,求收集nn种邮票的期望花费

解决方法

先设f[i]f[i]表示买到ii种邮票后,离买到nn种邮票的期望还差天数
和最上面那题一样的处理方法
考虑当前买了ii张邮票,再买一张邮票,有两种情况

  1. in\frac{i}{n}的概率买到重复的邮票,此时仍只买到ii张邮票
  2. nin\frac{n-i}{n}的概率买到没买过的邮票,此后就已买到i+1i+1张邮票

需要注意的是,无论哪种情况,都过了一天
所以有
f[i]=inf[i]+ninf[i+1]+1f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1
将其化简
f[i]=f[i+1]+nnif[i]=f[i+1]+\frac{n}{n-i}

初值f[n]=0f[n]=0,答案为f[0]f[0]
应逆向循环

当然这只是期望天数,不是期望花费
g[i]g[i]表示 拥有(不是买)ii种邮票, 买到nn种邮票的期望花费
考虑当前拥有了ii张邮票,买一张邮票,有两种情况

  1. in\frac{i}{n}的概率买到重复的邮票,此时仍只拥有ii
  2. nin\frac{n-i}{n}的概率买到没买过的邮票,此后就已拥有i+1i+1张邮票

需要注意的是,无论哪种情况,都买了一张邮票
此时我们不知道每张邮票多少钱
但我们知道每张邮票和过了多少天有关
这次的注意写在前面,我们是认为有了ii张邮票后才开始,所以第一天邮票价格为11
为什么这么设?
我们不知道也不好处理出前面买了多少张邮票,再买到一张邮票要多少钱
但是我们知道第一天肯定是只要11元的,答案为g[0]g[0],中间的过程不重要,只需推出最终答案
我们借助初始状态的这条非常有用的性质于是就设出了这样的gg
这样我们可以知道

  1. 若买到重复的邮票,我们知道,因为是设当前是第一天,所以原本希望买到的邮票的天数又往后推了一天,所以总价格要多f[i]f[i]元,还要加上自己的11
  2. 若买到没买过的邮票,同理,因为后面的g[i+1]g[i+1]也是从第11天开始考虑的,所以原本希望买到的邮票数也往后推了一天,所以价格要多f[i+1]f[i+1]元,还要加上自己的11

所以有

  1. g[i]+=in(g[i]+f[i]+1)g[i]+=\frac{i}{n}(g[i]+f[i]+1)
  2. g[i]+=nin(g[i+1]+f[i+1]+1)g[i]+=\frac{n-i}{n}(g[i+1]+f[i+1]+1)

总写下来就是g[i]=in(g[i]+f[i]+1)+nin(g[i+1]+f[i+1]+1)g[i]=\frac{i}{n}(g[i]+f[i]+1)+\frac{n-i}{n}(g[i+1]+f[i+1]+1)

将其化简得到
g[i]=inif[i]+g[i+1]+f[i+1]+nnig[i]=\frac{i}{n-i}f[i]+g[i+1]+f[i+1]+\frac{n}{n-i}

初值g[n]=0g[n]=0,答案为g[0]g[0]
应逆向循环


如有哪里讲得不是很明白或是有错误,欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
如能得到推荐博主就更开心了
您的鼓励是博主的动力

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->