对于概率dp，我一直都弄得不是特别明白，虽然以前也有为了考试去突击过，但是终究还是掌握得不是很好，所以决定再去学习一遍，把重要的东西记录下来。

1.hdu4405

Description

在一个 \(1*n\) 的格子上掷色子，从 \(0\) 点出发，掷了多少前进几步，同时有些格点直接相连，即若 \(a\) ，\(b\) 相连，当落到 \(a\) 点时直接飞向 \(b\) 点。求走到 \(n\) 或超出 \(n\) 期望掷色子次数

Solution

这道题目有助于理解为什么期望通常是逆推的。

如果是正推的话，对于每一个作为终点的点，它的起点可能会有很多，所以不方便于计算，并且，就算是统计出了所有以该点为终点的线路的起点，由这些起点过来的路径并不是所有可以到达该点的路径，因为掷骰子的时候，有可能恰好跳过了所有的起点然后到了这个点。

而逆推，每一个点所影响到的点是确定的，所以就很好计算。

其实也就是到达每一个格子的方案很多，但是从每一个格子出去的方案则是确定的。

对于 \(dp[i]=1+\sum dp[j]\) 其中 \(j\) 为可以从 \(i\) 到达的点，为什么这个式子是合法的呢？因为后面的 \(\sum\) 计算的是之前的步数，即它所代表的含义是步数，然后再加上这个 \(1\) 就好了。

code

2.hdu4418

Description

一个人站在编号为 \(0..n-1\) 的数轴上来回走动（假设 \(n\) 为 \(4\) ，那么，它的走动线路为 \(0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, ...\) ），以 \(p[i]\) 的概率走 \(i\) 步 \((i∈[1,m]，且∑p[i]=1)\) ，给出 \(n,m\) 以及起点和终点，求出这人走到终点的期望步数。

Solution

这个上面写得蛮详细的，我就偷一下懒吧。
博客

code

3.hdu4336

Description

在每包零食里面，可能有一张卡片，也可能没有。已知有总共有n张卡片，第i张的卡片出现的可能是 \(p_i\)。 问收集齐所有的卡片需要吃的零食数的期望是多少。

Solution

现将问题简化，如果只有一种卡片，设需要吃 \(E\) 包零食，那么可以得到
\[E=1*p+(1-p)*(E+1)\]

如果吃的第一包零食有卡片，那么期望就是 \(1*p\) ，如果第一包没有，则在算上这一包的基础上还需要更多包零食，还需要多少呢，显然为 \(E\) ，那么这样期望就是 \(1*(E+1)\) 。

因为 \(n\) 很小，所以考虑状压，设 \(E[i]\) 为 \(i\) 中的卡片已经收集到了，到所有的卡片全部收集完还需要的期望步数。那么，根据全期望公式，可以得到
\[E[i]=\sum_{j \notin i} p[j]*(1+E[i|(1<<j)])+(1-\sum_{j \notin i}p[j])*(E[i]+1)\]

再举一个 \(n=2\) 的特例
对于两张卡片
设 \(E(00)\) 表示还未集齐所有卡片到集齐所有卡片 \((11)\) 需要购买零食的期望
\(E(10)\) 表示已经集齐第一种卡片，到集齐所有卡片 \((11)\) 需要构面零食的期望

那么，
\(E(00)=p_1*(1+E(10))\) //买了第一包零食摸到了第1张卡片，概率是 \(p_1\) ,接下来还需要 \(E(10)\) 包零食
\(+p_2*（1+E(01))\) //买了第一包零食摸到了第2张卡片，概率是 \(p_2\) ,接下来还需要 \(E(01)\) 包零食
\(+（1-p1-p2)(1+E(00))\) //买了第一包零食,里面什么也没有，概率是 \(1-p_1-p_2\) ,接下来还需要 \(E(00)\) 包方便面

\(E(01)=p1*(1+E(11)) +(1-p1-p2) *(1+E(01))\)
\(E(10)=p2*(1+E(11))+(1-p1-p2)*(1+E(10))\)
\(E(11)=0\) //已经集齐了，当然只要买0包零食就行了。

code

4.poj2151

Description

有n支参赛队，共有m道题目。组委会期望，每一个参赛队至少解决1道题目，并且冠军队，至少解决t道题目。给出每个参赛队解决每道题目的概率，求满足期望的概率为多少。

Solution

其实可以忽略冠军队这个概念，直接将题目转化为：每一个参赛队至少解决1道题目，并且至少有一支参赛队至少解决t道题目。

直接求有一点麻烦，所以很容易产生一种套路的想法：求每一个参赛队至少解决1道题目的概率 \(p_1\) ，以及所有参赛队解决的题目的数量均在 \(0 ... n-1\) 的范围之内的概率 \(p_2\)，然后用 \(p_1-p_2\) 就是答案了。

不能设出这样的 \(dp\) 方程，设 \(dp[i][j][k]\) 为第 \(i\) 支参赛队伍，当前做到了第 \(j\) 道题目，一共解决了 \(k\) 道题目的概率。转移也很显然：
\[dp[i][j][k]=dp[i][j-1][k-1]*p[i][j]+dp[i][j-1][k]*(1-p[i][j])\]

然后
\[p_1=\prod_{i=1}^{n}(\sum_{j=1}^{m}dp[i][m][j])\]

\[p_2=\prod_{i=1}^{n}(\sum_{j=1}^{t-1}dp[i][m][j])\]

\[Ans=p_1-p_2\]

code

5.hdu4035

Description

有n个房间，由n-1条隧道连通起来，实际上就形成了一棵树，从结点1出发，开始走，在每个结点i都有3种可能：
1.被杀死，回到结点1处（概率为ki）
2.找到出口，走出迷宫 （概率为ei）
3.和该点相连有m条边，随机走一条
求：走出迷宫所要走的边数的期望值。

Solution

这道题的小数据，我本来是想用高斯消元去做的，但是不知道为什么有问题。
code

设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。

叶子结点：
\(E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1);\)
\(= ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei);\)

非叶子结点：（m为与结点相连的边数）
\(E[i] = ki*E[1] + ei*0\)
\(+ (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) );\)
\(= ki*E[1] + (1-ki-ei)/m*E[father[i]]\)
\(+ (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei);\)

设对每个结点：\(E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;\)

对于非叶子结点i，设j为i的孩子结点，则
\(∑(E[child[i]]) = ∑E[j]\)
\(= ∑(Aj*E[1] + Bj*E[father[j]] + Cj)\)
\(= ∑(Aj*E[1] + Bj*E[i] + Cj)\)

带入上面的式子得
\((1 - (1-ki-ei)/m*∑Bj)*E[i] =\)
\((ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] +\)
\((1-ki-ei) + (1-ki-ei)/m*∑Cj;\)

由此可得
\(Ai = (ki+(1-ki-ei)/m*∑Aj) / (1 - (1-ki-ei)/m*∑Bj);\)
\(Bi = (1-ki-ei)/m / (1 - (1-ki-ei)/m*∑Bj);\)
\(Ci = ( (1-ki-ei)+(1-ki-ei)/m*∑Cj )\)
\(/ (1 - (1-ki-ei)/m*∑Bj);\)

对于叶子结点
\(Ai = ki;\)
\(Bi = 1 - ki - ei;\)
\(Ci = 1 - ki - ei;\)

从叶子结点开始，直到算出 A1,B1,C1;

\(E[1] = A1*E[1] + B1*0 + C1;\)
所以
\(E[1] = C1 / (1 - A1);\)
若 A1趋近于1则无解...

code

6.hdu4089

Description

有n个人排队等着在官网上激活游戏。Tomato排在第m个。
对于队列中的第一个人。有一下情况：
1、激活失败，留在队列中等待下一次激活（概率为p1)
2、失去连接，出队列，然后排在队列的最后（概率为p2）
3、激活成功，离开队列（概率为p3）
4、服务器瘫痪，服务器停止激活，所有人都无法激活了。
求服务器瘫痪时Tomato在队列中的位置<=k的概率

Solution

设 \(dp[i][j]\) 为当时队列中共有 \(i\) 个人排队，Tomato排在第 \(j\) 个，系统瘫痪时的他的排名小于等于 \(k\) 的概率。这里需要明白一点，这个并不是指的系统在此刻瘫痪，而是在当前状态之下经过若干变换之后，瘫痪的时候排名小于等于 \(k\) 。
那么我们最后需要求的答案，就是 \(dp[n][m]\)

\(dp\) 方程很显然：
\[j==1:dp[i][1]=p_1*dp[i][1]+p_2*dp[i][i]+p_4*1\]

\[2 \leq j \leq k:dp[i][j]=p_1*dp[i][j]+p_2*dp[i][j-1]\]

\[+p_3*dp[i-1][j-1]+p_4*1\]

\[k<j \leq i :dp[i][j]=p_1*dp[i][j]+p_2*dp[i][j-1]+p_3*dp[i-1][j-1]\]

对于第二的方程，做一点解释。
根据全概率公式
\[P(A)=\sum P(B_i)*P(A|B_i)\]

其中 \(B_i\) 两两互斥
在发生第一个事件的时候，发生此事的概率为 \(p_1\) ，在发生此事之后，为了达到目标的概率显然为 \(dp[i][j]\) 那么两者相乘即可。
发生第二个事件的时候，由于序列中的第一个人走到了最后一个，所以在发生此事之后的概率为 \(dp[i][j-1]\) ，因为总人数是没有变的，Tomato肯定不是第一个，而他的排名又进了一位。
发生第三个事件的时候，第一个人出去了，总人数和排名同时改变了，所以就是 \(dp[i][j]\)
发生第四个事件的时候，因为已经达到了目标状态，所以显然发生此事之后的概率为 \(1\)

设 \(P_2=p_2/(1-p_1)\)，\(P_3=p_3/(1-p_1)\)，\(P_4=p_4/(1-p_1)\)

然后化简：
\[j==1:dp[i][1]=P_2*dp[i][i]+P_4\]

\[2 \leq j \leq k:dp[i][j]=P_2*dp[i][j-1]+P_3*dp[i-1][j-1]+P_4\]

\[k<j \leq i:dp[i][j]=P_2*dp[i][j-1]+P_3*dp[i-1][j-1]\]

这里有一点麻烦，因为如果需要求出 \(dp[i][1]\) ，就必须要首先求出 \(dp[i][i]\) 。因为每一个式子的后一部分与 \(dp[i]\) 无关，所以可以先求出来。

\[j==1:dp[i][1]=P_2*dp[i][i]+c[j]\]

\[2 \leq j \leq k:dp[i][j]=P_2*dp[i][j-1]+c[j]\]

\[k<j \leq i:dp[i][j]=P_2*dp[i][j-1]+c[j]\]

推一推式子，可以很容易地得到快速得到 \(dp[i][i]\) 的方法，然后再得到 \(dp[i][1]\) ，最后顺推回来即可。
最后判断一种特殊情况，在 \(p_4<0\) 的时候，直接输出 \(0\) 即可。

code

7.poj2096

Description

一个软件有s个子系统，会产生n种bug
某人一天发现一个bug,这个bug属于一个子系统，属于一个分类
每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n
问发现n种bug,每个子系统都发现bug的天数的期望。

Solution

dp[i][j]表示已经找到i种bug,j个系统的bug，达到目标状态的天数的期望
dp[n][s]=0;要求的答案是dp[0][0];

转移：
\(dp[i][j]\)，发现一个bug属于已经有的i个分类和j个系统。概率为\((i/n)*(j/s)\)
\(dp[i][j+1]\)，发现一个bug属于已有的分类，不属于已有的系统。概率为\((i/n)*(1-j/s)\)
\(dp[i+1][j]\)，发现一个bug属于已有的系统，不属于已有的分类，概率为\((1-i/n)*(j/s)\)
\(dp[i+1][j+1]\)，发现一个bug不属于已有的系统，不属于已有的分类，概率为
\((1-i/n)*(1-j/s)\)

8.poj3744

Description

在一条路上，起点在1处。在N个点处布有地雷，\(1 \leq N \leq 10\)。地雷点的坐标范围：\([1,100000000]\)
每次有p的概率前进1步，1-p的概率前进2步。问顺利通过这条路的概率。就是不要走到有地雷的地方。

Solution

设 \(dp[i]\) 为到达 \(i\) 号点的概率。
那么很显然可以得到：
\[dp[i]=p*dp[i-1]+(1-p)*dp[i-2]\]

但是由于坐标的范围非常大，所以需要矩阵优化。

设 \(x\) 数组中保存所有地雷的坐标，矩阵为 \(S\)
用 \(n\) 个点将道路分为 \(n+1\) 段
\(x[0]=0\)
\(x[0]+1...x[1]\)
\(x[1]+1...x[2]\)
...
\(x[n-1]+1...x[n]\)
每一段只有一个地雷，所以我们只要求得通过每一段的概率。乘法原理相乘就是答案。对于每一段，通过该段的概率等于1-踩到该段终点的地雷的概率。
那么
\[dp[x[1]]=S^{x[1]-x[0]-1}\]

\[dp[x[1]+1]=1-dp[x[1]]=1-S^{x[1]-x[0]-1}\]

下一段成功通过的概率为
\[dp[x[2]+1]=dp[x[1]+1]*(1-S^{x[2]-x[1]-1})\]

\[=(1-S^{x[1]-x[0]-1})*(1-S^{x[2]-x[1]-1})\]

所以
\[dp[x[n]+1]=\prod_{i=1}^{n}(1-S^{x[i]-x[i-1]-1})\]

最后矩阵优化就好了
code