概率dp入门
概率dp
概率dp有两种题型,一种是求概率一种是求期望。
来结合一下题目
Aeroplane chess
题意
一个人在一条线上掷骰子,在线上有类似飞行棋的可以直接到达某个点的特殊点,问从$0$到$n$掷骰子次数的数学期望是多少?
题解
期望dp,dp最重要的就是从一个已知的最优状态转化到另一个最优状态。
为什么期望要反着求呢,因为你并不知道$dp[0]$这个点的值,因为我们定义$dp[x]$为$x$点到$n$点的掷骰子数的数学期望。而$dp[n]$的数学期望我们是知道的,是0,因为已经在$n$点了。之后我们倒推前面点的数学期望,因为你骰子是6面,从一个点可以到后面的六个点并且是等概率的,所以
$dp[i] = \sum_{j=i+1}^{i+6}dp[j]/6+1$
而且如果是特殊的飞行点,那么他的数学期望直接就是他的到的点的数学期望。
+2:没有从n-1开始,居然sb到从n开始计算。
AC代码
1 |
|
B - Discovering Gold
题意
跟上面的差不多,就是求期望。
题解
跟上面基本相似。
AC代码
1 |
|