Algorithm‧ICPC‧Programming: PKU3744 Scout YYF I

本題是POJ月賽八月份題。

題意是某人在整數線上向前走。一開始時他站在第一格。給出向前跳一格的概率為 $p$ 、兩格的概率為 $q$ 、其中 $p+q = 1$ 。同時給出 $N$ 個不可以停留的格子 ${f_n}$ ，問能跳過這 $N$ 個格子的概率是多少。
假設 $P(i)$ 為當前在第 $i$ 格的概率。若果對基本概率有認識的話，不難發現如下關係﹕
$P(i) = pP(i-1) + qP(i-2)\quad \mbox{s.t.} P(1) = 1, P(2) = p$

由此即可以線性時間求出 $P(f_1-1)$ 。然後要跨過 $f_1$ 的話， $P(f_1+1) = qP(f_1-1)$ 。
如此一來解決 $P(f_2-1)$ 的問題出現重疊，解法一致，也可以應用於所有 $f_i$ 。求出答案即是求 $P(f_N+1)$ 。

不過在時限內利用線性時間求出答案還是很勉強。不難留意上述公式其實是一個線性遞迴式，由此可以利用矩陣表示其關係﹕
$\begin{pmatrix} p & q \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} P(i+1) \\ P(i) \end{pmatrix} = \begin{pmatrix} P(i+2) \\ P(i+1)Â \\ \end{pmatrix}$
想求出 $P(f_1-1)$ 的話則可以利用矩陣乘法，在 $\mathcal{O}(\lg N)$ 的時間以如下算式求出﹕
$\begin{pmatrix} p & q \\ 1 & 0 \\ \end{pmatrix}^{f_1-1} \begin{pmatrix} 1 \\ 0 \\ \end{pmatrix}$

請特別留意當 $f_1 = 1$ 的情況。

還有，死活過不了的朋友，請先為 $f$ 做一遍排序…

Algorithm‧ICPC‧Programming

2009年9月8日星期二

PKU3744 Scout YYF I

沒有留言:

網誌存檔

關於我自己