POJ 3744 Scout YYF I（矩阵优化的概率DP）

773 浏览 0 回复 2019-11-29

Water_Fox

+关注

3744 -- Scout YYF I

http://poj.org/problem?id=3744

Virtual Judge链接：https://vjudge.net/problem/POJ-3744

分析 : 转移方程就是很显然的一个递推， $f\left[ i \right]=f\left[ i -1\right]*p+f\left[ i-2 \right]*\left( 1-p\right)$ ，但是坐标的范围有1e8，不能直接做，所以要优化，线性的递推用矩阵加速是很常见的方法，所以构造出矩阵乘法 $\left[ f\left( i-2 \right) ,f\left( i-1 \right)\right]*\left[ \begin{matrix} 0 & 1-p \\ 1 & p \\ \end{matrix} \right]=\left[ f\left( i-1 \right),f\left(i \right) \right]$ ，递推的复杂度可以变为log级别，然后我们按mine位置分段，每两个mine之间矩阵递推一次，n次之后可以得到答案。

code: