题解：P14508 猜数游戏 guess【背包，最短路】

考虑第一次获得的有效信息，一定是对于某个 $x\in[1,n)$，得知目标位置在 $[1,x]$ 还是 $(x,n]$，发现可以递归到子问题。

于是，设 $f(i,0/1)$ 表示：得知目标位置在 $[1,i]$ 后，当前棋子在 $1$ 或 $i+1$，的最小答案。

转移有：

$w(x)$ 表示：用 $m$ 种移动方式移动 $x$ 格的最小消耗。可以用最短路预处理。

分析一下复杂度。目前在 DP 转移中能用到的 $w(x)$ 的定义域是 $O(n)$ 的，对于 $w(x)$ 的某种移动方案，一定可以交换移动顺序（两个方向交替排列），使得每一步距离起点都是 $O(n)$ 的。因此预处理用到的 $w(x)$ 的定义域也是 $O(n)$。

目前复杂度为 $O(T(n^2+nm))$。常数略微大一点就过不了了。

记 $V=\max a$，假设当前问题为 $f(i,0)$，如果棋子往中间移动了 $>V$ 的距离，那么在获得这一信息之前，一定存在一个 $\le V$ 的移动距离已经获得信息了，因此 DP 转移可以写为：

于是 $w(x)$ 的定义域被缩小到了 $O(V)$。总复杂度 $O(T(nV+mV))$，分别为 DP 和最短路的复杂度。

然后 $f$ 状态中的 $0/1$ 其实没什么用，可以直接记 $f(i)$，转移为：