题目大意

一个$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]$
应逆向循环

题目大意

有$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]$
应正向循环

题目大意

桌面上有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]$
应正向循环

题目大意

给出$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$，答案在中途计算
应正向循环

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

题目大意

有$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]$
应逆向循环

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