P4745 [CERC2017]Gambling Guide

Problem $1 \le n,m \le 300000$ Solution 考虑设$dp_x$为$x$到$n$的最小硬币期望值。 $dp_n = 0$ \(dp_x = \left(\sum \min\{dp_v,dp_x\}\right) \cdot \dfrac{1}{deg_x}