期望DP

[也许更好的阅读体验](https://www.cnblogs.com/Morning-Glory/p/11228082.html) [也许更好的阅读体验](https://www.cnblogs.com/Morning-Glory/p/11228082.html) --- # 数学期望 ## 符号 $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$元的。 --- # 转移方程 几种常见设转移方程数组的方法 1. 设$f[i]$表示的是由$i$状态变成 __最终__ 状态的期望 2. 按照题意直接设 3. 把选择的东西加入数组，如$f[i][j]$表示第$i$个物品选$j$个的期望或$f[i][j]$表示有$i$个$A$物品，$j$个$B$物品的期望 求转移方程 应优先考虑进行操作后当前状态会怎么样，而不是如何变成当前状态，即先考虑 __逆向__ 如果逆向没有思路，则考虑 __正向__ --- # 经典例题 注：没有贴出代码，有些题目现在找不到了 ~~(至少博主没有找到)~~，也有博主自己想的题目 ~~(很水)~~，如博主有写代码则已放进标题的链接里，那些链接都是题解，不是原题链接 ## [SP1026FavoriteDice](https://blog.csdn.net/Morning_Glory_JR/article/details/96729291) ## 题目大意 一个$n$面的骰子，求期望掷几次能使得每一面都被掷到 ## 解决方法 设$f[i]$表示已经掷到过$i$面，__还__ 期望掷多少次骰子使每一面都被掷到 现在掷一次骰子，有两种情况 1. 有$\frac{i}{n}$的概率掷到已经掷到过的面，此时仍然还要掷$f[i]$次骰子 2. 有$\frac{n-i}{n}$的概率掷到没掷到过的面，此后就掷到过$i+1$个面了，还需掷$f[i+1]$次骰子 需要注意的是，无论是掷到以上哪种情况，都需要掷一次骰子 所以有 $f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1$ 将其化简 $f[i]=f[i+1]+\frac{n}{n-i}$ 初值$f[n]=0$，答案为$f[0]$ 应逆向循环 --- ## [涂格子/小孩和礼物](https://blog.csdn.net/Morning_Glory_JR/article/details/96752187) ## 题目大意 有$n$个格子，每次等概率随机给一个格子染色，问涂$m$次后期望有多少格子被染色了 ## 解决方法 设$f[i]$表示涂$i$次后期望有多少格子被染色了 现在进行第$i$次染色，仍然有两种情况 1. 有$\frac{f[i-1]}{n}$的概率涂到已经涂过的格子 2. 有$\frac{n-f[i-1]}{n}$的概率涂到没涂过的格子 需要注意的是，无论是以上哪种，都已经有$f[i-1]$个格子被染色了 所以有 $f[i]=\frac{f[i-1]}{n}·0+\frac{n-f[i-1]}{n}·1+f[i-1]$ 将其化简 $f[i]=\frac{n-f[i-1]}{n}+f[i-1]=\frac{n-1}{n}f[i-1]+1$ 此时该式就是一个等差数列套等比数列 于是我们可以求其通项公式，博主懒得求了写下大致过程 >令$k=\frac{n-1}{n}$ $f_n=kf_{n-1}+1$ $f_n+\frac{1}{k-1}=kf_{n-1}+\frac{k}{k-1}$ $f_n+\frac{1}{k-1}=k(f_{n-1}+\frac{1}{k-1})$ 令$g_n=f_n+\frac{1}{k-1}$ 则$g_n=kg_{n-1}$ 怎么求$g_n$就不用说了吧 $f_n=g_n-\frac{1}{k-1}$ $f_n$也能求出来了 初值$f[0]=0|f[1]=1$答案为$f[m]$ 应正向循环 --- ## [简单题](https://blog.csdn.net/Morning_Glory_JR/article/details/96867261) ## 题目大意 桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。 ## 解决方法 设$f[i][j]$表示有$i$张红牌，$j$张黑牌的期望收益 考虑翻一张牌，还是有两种情况 1. 有$\frac{i}{i+j}$的概率翻到红牌，此后就只有$i-1$张红牌，$j$张黑牌 2. 有$\frac{j}{i+j}$的概率翻到黑牌，此后就只有$i$张红牌，$j-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,\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]=1$，答案为$f[R][B]$ 应正向循环 --- ## [亚瑟王](https://blog.csdn.net/Morning_Glory_JR/article/details/96857136) ## 题目大意 给出$n$个技能，每个技能按输入顺序有$p[i]$的概率释放并造成$d[i]$的伤害。每轮游戏从前往后顺序查看每个技能，若技能发动过则跳过，没发动过则以$p[i]$的技能发动，即每个技能只能发动一次，若将一个技能发动，则进行下一轮游戏，没有成功发动或被跳过就查看下一个技能，一轮游戏可能每个技能都不发动，问$r$轮游戏一共能造成的伤害期望。 ## 解决方法 因为有一个顺序查看的限制，没有后效性的状态是十分不好设的，因为不知道前面有几个技能发动了，若一个技能前面的技能在某轮发动了，则该技能本轮一定不能发动，若前面有些技能发动过，则它们都会被跳过 为了解决这种情况，我们设状态时试着强制限制技能发动（$nr$枚举情况），当然，设的状态仍然要满足 __所有__ 情况都考虑在内 设$f[i][j]$表示对前$i$个技能进行了$j$轮游戏发生的 __概率__ 若前$i$个技能进行了$j$轮游戏 则有$j$轮不会考虑第$i+1$个技能 即有$r-j$轮游戏选择了$i$之后的技能 此时考虑第$i+1$个技能的情况，分为两种 1. 有$p[i+1]^{r-j}$的概率$i+1$号技能从未发动 2. 有$1-p[i+1]^{r-j}$的概率$i+1$号技能发动过 需要注意的是，此时 __已经__ 确定前$i$个技能进行并 __只进行__ 了$j$轮游戏，其概率应该也计算在内 所以有 1. $f[i+1][j]+=1-p[i+1]^{r-j}f[i][j]$ 2. $f[i+1][j+1]+=(1-p[i+1]^{r-j})f[i][j]$ $j+1$要小于等于$r$ 初值$f[0][0]=1$，答案在中途计算 应正向循环 计算了概率，别忘了求的是期望伤害，在求概率的时候顺便用概率乘以伤害 --- ## 抽卡 ## 题目大意 $\mathcal{Morning\_Glory}$最近迷上了抽卡，每次抽卡抽到$6$星卡的概率为$p$。抽卡活动进行$n$天，在第$i$天要花$c[i]$游戏币进行抽卡。求$\mathcal{Morning\_Glory}$抽得$k$张$6$星卡数时的期望游戏币花费。 ## 解决方法 设$f[i][j]$表示第$i$天抽到$j$张$6$星卡的期望游戏币花费 在第$i$天进行抽卡，有两种情况 1. 有$p$的概率抽到$6$星卡 2. 有$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]$ 应正向循环 --- ## [收集邮票](https://blog.csdn.net/Morning_Glory_JR/article/details/96892401) ## [[POJ3682]King Arthur's Birthday Celebration](https://blog.csdn.net/Morning_Glory_JR/article/details/96898944) 这两题是一样的类型，只有概率与计算答案要改一下，这里用收集邮票来做例题 ##题目大意 有$n$种邮票，每天等概率的买一张邮票，第$i$天购买要花费$i$元，求收集$n$种邮票的期望花费 ## 解决方法 先设$f[i]$表示买到$i$种邮票后，离买到$n$种邮票的期望还差天数 和最上面那题一样的处理方法 考虑当前买了$i$张邮票，再买一张邮票，有两种情况 1. 有$\frac{i}{n}$的概率买到重复的邮票，此时仍只买到$i$张邮票 2. 有$\frac{n-i}{n}$的概率买到没买过的邮票，此后就已买到$i+1$张邮票 需要注意的是，无论哪种情况，都过了一天 所以有 $f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1$ 将其化简 $f[i]=f[i+1]+\frac{n}{n-i}$ 初值$f[n]=0$，答案为$f[0]$ 应逆向循环 当然这只是期望天数，不是期望花费 设$g[i]$表示 __拥有__(不是买)$i$种邮票， __买到__$n$种邮票的期望花费 考虑当前拥有了$i$张邮票，买一张邮票，有两种情况 1. 有$\frac{i}{n}$的概率买到重复的邮票，此时仍只拥有$i$种 2. 有$\frac{n-i}{n}$的概率买到没买过的邮票，此后就已拥有$i+1$张邮票 需要注意的是，无论哪种情况，都买了一张邮票 此时我们不知道每张邮票多少钱 但我们知道每张邮票和过了多少天有关 这次的注意写在前面，我们是认为有了$i$张邮票后才开始，所以第一天邮票价格为$1$元 为什么这么设？ 我们不知道也不好处理出前面买了多少张邮票，再买到一张邮票要多少钱 但是我们知道第一天肯定是只要$1$元的，答案为$g[0]$，中间的过程不重要，只需推出最终答案 我们借助初始状态的这条非常有用的性质于是就设出了这样的$g$ 这样我们可以知道 1. 若买到重复的邮票，我们知道，因为是设当前是第一天，所以原本希望买到的邮票的天数又往后推了一天，所以总价格要多$f[i]$元，还要加上自己的$1$元 2. 若买到没买过的邮票，同理，因为后面的$g[i+1]$也是从第$1$天开始考虑的，所以原本希望买到的邮票数也往后推了一天，所以价格要多$f[i+1]$元，还要加上自己的$1$元 所以有 1. $g[i]+=\frac{i}{n}(g[i]+f[i]+1)$ 2. $g[i]+=\frac{n-i}{n}(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]=\frac{i}{n-i}f[i]+g[i+1]+f[i+1]+\frac{n}{n-i}$ 初值$g[n]=0$，答案为$g[0]$ 应逆向循环 ___ >如有哪里讲得不是很明白或是有错误，欢迎指正 如您喜欢的话不妨点个赞收藏一下吧