被创飞了。/ll
题意
飞船从 \(0\) 出发，速度为 \(1\)。路线上有加油站，根据种类可以提供 \(\times 1 \times 2 \times 3 \times 4\) 的加速。\(q\) 次询问到达 \(y\) 的最短时间。
分析
考虑 DP。令 \(f(i,j)\) 表示到第 \(i\) 个加油站，速度为 \(j\) 的最短时间，转移显然。
速度的极限是 V，下证：
注意到提供的加速本质上只有 \(\times 2 \times 3\) 两种。那么速度可以表示为 \(2^p 3^q\)。于是我们的第二维可以拆成两维。这样的状态就是 \(O(n \log^2 V )\) 的了，转移依然是 \(O(1)\)。
标签：短时间,P11290,times,加油站,速度,两维 From： https://www.cnblogs.com/tai-chi/p/18551704