初中课本知识已经有讲概率啦！应用在信息学里面可以这样↓

我们现在假装要从出生点出发去新日$♂$暮里，有两种方法

1. 老司机开车带我们去，费用是一千软妹币，绝对不翻车

2. 年轻司机开车带我们去，费用是一百软妹币，但是有$0.5$的概率会翻车被查。因此我们要回到出生点，此时只能让老司机带我们飞【捂眼

上谁的车呢？

权衡利弊之后，我们应当先上年轻司机的车试试看

此时年轻司机有$0.5$的概率成功，期望是$0.5 \times 100=50$

另外，$0.5$的概率是年轻司机被查之后我们去找老司机帮忙，期望是$0.5\times (100+1000)=550$

那么最终期望就是$550+50=600$

【bzoj4318】$OSU!$——初步接触期望$dp$

题目大意

给定一个数列$S$，长度为$n$

给出$a_i$，$S_i$有$a_i$的概率是$1$，否则是$0$

如果得分是数列$S$中所有连在一起的$1$的长度的立方和，询问得分的期望

数据范围

$n\leqslant 100000,0\leqslant a_i\leqslant 1$

题解

设转移到$S_i$时，$S_1,S_2...S_i-1$中连在一起的$1$的最长后缀长度为$x$

易证，如果$S_i=0$，则贡献为$0$，如果$S_i=1$，则贡献为$(x+1)^3-x^3=3x^2+3x+1$

只需要考虑对答案有所影响的情况

因此只要考虑，当$S_i=1$时，$x^2$和$x$的期望加起来，转移到$S_{i+1}$的期望即可

阅读更多……

题目大意

一共有$n$个城镇，第$i$个城镇到第$i+1$个城镇有一条收费$c_i$的单向道路

除此之外，再给出$m$个单向传送门，可以从传送门规定的起始地去往目的地，同样需要收费$w_j$

但它传送成功的概率只有$p_j$，失败会传送回起始地，并且无论成败，使用了传送门就需要花费$w_j$

现在若要从第$1$个城镇前往第$n$个城镇，询问最小期望花费

阅读更多……