[动态规划]概率与期望

经典问题：约瑟夫环

有n个人下标为0至n-1，从1开始报数，报到m-1的人退出，剩下的人继续从0开始，则最后一个剩下的人的编号是多少。

[解法]：第一个人退出的下标必定是$$(m \mod n) -1​$$,剩下的n-1个人重新组成一个环，以下标为$$k=m \mod n​$$开始。

令$$f_i$$表示i个人玩游戏最后退出的人的下标，则只需求$$f_n$$:

​ $$f1=0,f_i=(f{i-1}+m)\mod i(i \ge 1)$$

概率

1.[JLOI2013]卡牌游戏

[解法]：令$$f{i,j}$$表示i个人游戏，j获胜的概率，枚举每次抽中的卡牌。$$f{1,1}=100$$

​ 若k退出，则新一轮j的位置$$p=[(j-k+i-1)\mod i ]+1$$, 当$$k \not= j$$时，$$f{i,j}= \sum^m _1\frac{f{i-1,p}}{m}$$.

2.[POJ3744]Scout YYF I

[题意]：一条有地雷的路上，起点在1，在n个点出布有地雷$$([1,100000000])$$,每次前进1步的概率为p,前进2步的概率为1-p,求顺利通过此路的概率。

[解法]：令$$fi$$为到达i出的概率，很容易推出$$f_1=1,f_i=pf{i-1}+(1-p)f_{i-2}$$,但由于坐标轴范围广，因此需要分段计算。

​ 令$$x_i$$表示mine分布的坐标，将道路分成n段，为：

​ $$(1 \cdots x1),(x_1+1 \cdots x_2),(x_2+1 \cdots x_3),\cdots,(x{n-1}+1 \cdots x_n)$$

每段只有一个mine，只需求出通过每一段的概率，然后相乘(乘法原理)。

对于求每一段的概率运用矩阵乘法即可。

期望

一般采用逆序方式定义状态：从当前状态到最终状态的代价

1.[BZOJ3036]绿豆蛙的归宿

[题意]：给定起点为1终点为n的有向无环图，到达每个顶点时，有k条离开改点的道路，可以选择任意一条离开且选每条路的概率为$$\frac{1}{k}$$,求从起点到终点走过路径的长度期望总和。

[解法]：令$$f_i$$表示从i点出发到终点n的期望总长度，$$G_i$$表示第i个点离开的道路的集合，$$e$$为边的信息。则：

$$ fi= \sum {e \in Gi} \frac{f{e{to}}+e{val}}{G_i}

$$ 达到每个点的状态可以用dfs序或拓扑序。

2.[BZOJ3450]Tyvj1952 Easy

[题意]：给定ox序列，某些位置不固定，连续k长度的o会增加$$k^2$$收益,求序列最大收益。

[解法]：分情况讨论：

​ 令$$E_i$$表示到第i个的期望，$$len_i$$表示到第i的期望长度，则：

$$ \begin{equation} si=o,E_i=E{i-1}+(len{i-1}\cdot 2+1),len_i=len{i-1}+1\si=x ,E_i=E{i-1},leni=0\ s_i=?,E_i=E{i-1}+\frac{len{i-1} \cdot 2+1}{2} ,len_i=\frac{len{i-1}+1}{2} \end{equation}

$$

3.[HDU3853]LOOPS

[题意]：给定矩阵$$r\times c$$,从$$(1,1)$$到$$(r,c)$$,在$$(i,j)$$处，有$$P_1(i,j)$$的概率停留在原地，$$P_2(i,j)$$的概率到$$(i,j+1)$$,$$P_3(i,j)$$的概率到$$(i+1,j)$$,每次需要2消耗，求消耗的期望。

[解法]：令$$E_{i,j}$$表示从(i,j)到(r,c)的消耗期望，则：

$$ E{i,j}=E{i,j}P{1{i,j}}+E{i,j+1}P{2{i,j}}+E{i+1,j}P_{3{i,j}}

$$ 移项便可得：

$$ E{i,j}=\frac{E{i,j+1}P{2{i,j}}+E{i+1,j}P{3{i,j}}}{1-P{1{i,j}}}

$$