题目大意：

有个人每天要去公司上班，每次会经过N条河，家和公司的距离为D，默认在陆地的速度为1，
给出N条河的信息，包括起始坐标p，宽度L，以及船的速度v。船会往返在河的两岸，人到达河岸时，
船的位置是随机的（往返中）。问说人达到公司所需要的期望时间。

思路：


1，过每条河最坏的情况是t=*L/v； 即去的时候船刚刚走。

2，过没条河最优的情况是t=L/v；    即去的时候船刚刚来。

3，由于船是均匀发布的，符合线性性质，所以平均下来，过每条河的时间t=*L/v。

题意：

甩一个n面的骰子，问每一面都被甩到的次数期望是多少。

思路：

比较简单常见，公式：初始化dp[]=0;  dp[i]=i/n*dp[i]+(n-i)/n*dp[i+1]+1;  化简逆推即可。  求的是dp[0];

题意：

有n个奖品，m个人排队来选礼物，对于每个人，他打开的盒子，可能有礼物，也有可能已经被之前的人取走了，然后把盒子放回原处。为最后m个人取走礼物的期望。

思路：


排队取，第1个人取到1个，dp[1]=1;后面的人dp[i]=p取到礼物盒子+dp前面的取到礼物盒子=(n-dp[i-1])/n + dp[i-1]；

当然，也可以化简为公式   printf("%.10lf\n",n*1.0*(1-pow((n-1)*1.0/n,m)));  

题意：

师傅被妖怪抓走了。有n个妖怪，每个妖怪有一个固定的战斗力c[]，师傅也有一个初始战斗力f0。
每天，师傅会随机选择一个妖怪决斗，如果打得赢ft>c[]，就可以逃出去,逃出去要t[]天，毕竟超人不会飞；
否则，师傅会不甘心，当天他会拿出秘籍练功，将自己变强,f(t+)=f(t)+c[]，第二天寻找下一次机会。
问师傅能够逃脱可怕的妖怪，继续追求去印度吃手抓饼的梦想的天数的数学期望day。

思路：

设dp[F]是战斗力为F时，逃离的天数期望。（答案是dp[f]）。则有公式。

dp[F]= Σ /n * t[i]              ,F>c[[i]

           +∑ /n * dp[F+c[i]]   ,F<=c[i]

题意：

师傅又被抓了，师傅现在在一个树里。第一天他在1号节点；对于每一个节点，
有三种可能，一是被妖怪杀死ki，二是被徒儿救走ei，三是第二天等概率地走到相邻的一个节点。
问师傅被救走的天数的期望，不能被救走输出“impossible”。

思路：

上一个题，由于是单调的，没有后续性，所以可以记忆化搜索或者DP解决。
这个题存在后续性，举个例子。如果求从s号节点逃出去的期望dp[s]，那么dp[s]和s的子节点和s的父节点有关，而欲求s的子节点时，子节点又和父节点s有关。。。

这个时候就需要我们找一个办法来排除后续性。大概就是找一个很牛逼的公式。这个公式本来是和后续性有关，但是公式之间抵消的后续性。

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

    叶子结点：

    E[i] = ki*E[] + ei* + (-ki-ei)*(E[father[i]] + );

         = ki*E[] + (-ki-ei)*E[father[i]] + (-ki-ei);

    非叶子结点：（m为与结点相连的边数）

    E[i] = ki*E[] + ei* + (-ki-ei)/m*( E[father[i]]+ + ∑( E[child[i]]+ ) );

         = ki*E[] + (-ki-ei)/m*E[father[i]] + (-ki-ei)/m*∑(E[child[i]]) + (-ki-ei);

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

对于非叶子结点i，设j为i的孩子结点，则

    ∑(E[child[i]]) = ∑E[j]

                   = ∑(Aj*E[] + Bj*E[father[j]] + Cj)

                   = ∑(Aj*E[] + Bj*E[i] + Cj)

    带入上面的式子得

    ( - (-ki-ei)/m*∑Bj)*E[i] = (ki+(-ki-ei)/m*∑Aj)*E[] + (-ki-ei)/m*E[father[i]] + (-ki-ei) + (-ki-ei)/m*∑Cj;

    由此可得

    Ai =        (ki+(-ki-ei)/m*∑Aj)   / ( - (-ki-ei)/m*∑Bj);

    Bi =        (-ki-ei)/m            / ( - (-ki-ei)/m*∑Bj);

    Ci = ( (-ki-ei)+(-ki-ei)/m*∑Cj ) / ( - (-ki-ei)/m*∑Bj);

    对于叶子结点

    Ai = ki;

    Bi =  - ki - ei;

    Ci =  - ki - ei;

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

    E[] = A1*E[] + B1* + C1;

    所以

    E[] = C1 / ( - A1);

    若 A1趋近于1则无解...

题意：

你知道，师傅经常被抓，这次又被抓到一个矩阵里面，最开始他在Map[][]，出口在Map[n][m]；
每一次他会消耗两颗神丹，然后每一个格子，有一定概率留在原地，有一定概率向下走一格，有一定概率向右走一格。。。求师傅逃出去的神丹消耗期望。

思路：

这次的逃亡很好想，没有前两次那样需要逆推或者求公式。聪明的你不如手动算一下。实在不行还可以参考下面的题目。

七：ZOJ3551Bloodsucker （数学期望）

 题意：

有三个骰子，面值分别是k1，k2，k3。每次扔出的值之和加到ans上，问多少次才能ans>n；当然，当遇到k1=a,k2=b,k3=c时，ans=;重新开始累加。

思路：

和之前第五题Maze一个题型。写出的公式是有后续性的。我们需要弄一个递推公式，消去后续性。（当然循环的话高斯消元也可以做。）

设dp[i]表示达到i分时到达目标状态的期望，pk为投掷k分的概率，p0为回到0的概率

则dp[i]=∑(pk*dp[i+k])+dp[]*p0+;

都和dp[]有关系，而且dp[]就是我们所求，为常数

设dp[i]=A[i]*dp[]+B[i];

代入上述方程右边得到：

dp[i]=∑(pk*A[i+k]*dp[]+pk*B[i+k])+dp[]*p0+

     =(∑(pk*A[i+k])+p0)dp[]+∑(pk*B[i+k])+;

     明显A[i]=(∑(pk*A[i+k])+p0)

     B[i]=∑(pk*B[i+k])+

     先递推求得A[]和B[].

     那么  dp[]=B[]/(-A[]);

 题意：

一对情侣开房玩抓老鼠游戏，老鼠有黑白两色，女的为先手，先抓到白老鼠胜。
特别的，男的每抓一只老鼠后，还会随机放走一只老鼠。问女的赢的概率是多少。如果输了，后果会很严重，当天晚上只能睡沙发。

思路：

dp[i][j]为当前状态，有i只白老鼠，j只黑老鼠，女的赢的概率。那么dp[][] = 这一次赢 + 以后赢=   i/(i+j) +  。。。具体见代码。

题意：

有一个富豪，他决定每天撒钱，并且抛硬币，第一天1块钱，第二天3块钱，第三天5块，直到他抛到硬币向上的数量为K。

求天数期望和钱期望。

思路：

天数期望dp很好求，公式一推，代码一敲。钱期望money没想出来，我开始想难道是用第x天结束的期望乘第x天的钱，累加，直到x天的期望乘钱小于0.。

但是参考了下别人的公式，反正自己是没想出来。

天数：dp[i]=dp[i]*(-p)+dp[i-]*p+，化简：dp[i]=dp[i-]+/p;

money：money[i] = p(money[i-]+  *(dp[i-]+)-) + (-p)(money[i] +  * (dp[i]+)-)。

化简：money[i]=money[i-]+*dp[i-]-*dp[i]+(+*dp[i])/p;

问题：


可以用巴斯卡分布？二项分布？？？给数学跪了

 http://blog.csdn.net/nmfloat/article/details/50650489

题意：

一套题，有T个题，M个人应考，已知每个人做来某题的概率。问X的概率。X满足，每个考生至少做来一道题。至少有一人做的题不少于N道。

思路：

不算是很典型的概率DP，更像是一道简单数学题。

可以把所有考生都至少做来一道题的概率减去 每个人都做来1到n-1道题的概率。

p=[(-x11)*(-x12)(..) ] * [(-x21)*(-x22)(..)]*[...]     -    [...]*[...] ，这样的话，用组合数就ok了。

但是这里是用的DP是思路，先把考生与考题的关系求出来，p[i][j][k] 表示第i个考试前j个题会做k道的概率。再根据题意进行DP。

描

大家对斐波那契数列想必都很熟悉:

a0 = , a1 = , ai = ai- + ai-,(i > )。

现在考虑如下生成的斐波那契数列:

a0 = , ai = aj + ak, i > , j, k从[, i-]的整数中随机选出（j和k独立）。

现在给定n，要求求出E(an)，即各种可能的a数列中an的期望值。(1<=n<=500)

思路：

不说了，数据小，我暴力枚举的。

描述

一日，崔克茜来到小马镇表演魔法。

其中有一个节目是开锁咒：舞台上有 n 个盒子，每个盒子中有一把钥匙，对于每个盒子而言有且仅有一把钥匙能打开它。
初始时，崔克茜将会随机地选择 k 个盒子用魔法将它们打开。崔克茜想知道最后所有盒子都被打开的概率。

，每个盒子都有一个入度和一个出度，以之前二分图拆点的经验来看，必然会形成很多个环。

，每个环至少选择一个盒子。

，每个环至少选择一个盒子的组合数，联想到母函数，组合数。

.*YY。可以DP，但是误差可能大一些。可以全部求出来再除，这样误差小一些。

 （ps：学会了母函数再搞组合是要多一分灵感！弯的four）

题意：一段连续长度为L的线段贡献是L^，求贡献的期望。 （注意期望的平方和求方的期望不一样

思路：此类期望题都是单独算某一位的贡献，假设前一位的连续长度为g[i-]，那么很明显当前位的期望长度为 g[i]=(g[i-]+)*p[i]；

则当前为的贡献是add=g[i]^-g[i-]^=*g[i]^-*g[i]+。 这三部分分别算期望即可。

   第一部分：*g[i]^，就是平方的期望（不仅仅是期望的平方那么简单），令期望的平方为数组g2，则3g2[i]=*(g2[i-]+*g[i-]+)*p[i];

   第二部分：-*g[i]，其期望=-*(g[i-]+)*p[i]

   第三部分:   ，其期望=p[i]


主要就是要注意期望的平方如何去算！