poj3744 Scout YYF I 概率dp

简单讲一下题目的意思吧

给定一个人在路上行走,他有p的概率走1步,有1-p的概率走2步,路上是有地雷的,求活着到达终点的概率

题解:

易得 f[n]=p\times{f[n-1]}+(1-p)\times{f[n-2]}

我们可以用矩阵快速幂来求解

但是由于我非常的懒

我就用一种特征值的做法来做

对于形如 f[n]=a \times f[n-1]+b \times f[n-2] 的方程

我们可以解出特征方程 x^2 = ax+b

于是我们可以解出这个方程的两个解 我们设它为x_1,x_2

于是 就有
x1=x2f[n]=(x1+x2n)a^n
否则 f[n]=x1a^n+x2b^n

f[0]=1,f[1]=p代入即可

PS:特征值还可以推斐波那契书的通项公式2333

One thought on “poj3744 Scout YYF I 概率dp

发表评论

电子邮件地址不会被公开。 必填项已用*标注