设 \(f_i\) 表示第一次到达 \(i\) 的所用时间，初始 \(f_1 = 0\)。
首先考虑运动的形态会是什么样子，应该是第一次走到 \(i\)，然后不断的跳 \(p_i\)，直到再一次走到 \(i\)，再向 \(i + 1\) 走。
其实转移是很好转移的，你可以看做跳到 \(p_i\) 就是第一次走到 \(p_i\) 往回跳的过程，所以转移应该是：
\[f_{i + 1} = f_i + (f_i - f_{p_i}) + 2
\]
模拟即可。
U636457 刺客
深耕网站建设、视觉设计与SEO优化的一线实战洞察。
设 \(f_i\) 表示第一次到达 \(i\) 的所用时间，初始 \(f_1 = 0\)。
首先考虑运动的形态会是什么样子，应该是第一次走到 \(i\)，然后不断的跳 \(p_i\)，直到再一次走到 \(i\)，再向 \(i + 1\) 走。
其实转移是很好转移的，你可以看做跳到 \(p_i\) 就是第一次走到 \(p_i\) 往回跳的过程，所以转移应该是：
模拟即可。