题解：P14508 猜数游戏 guess【背包，最短路】
chenwenmo
·
·
题解
考虑第一次获得的有效信息，一定是对于某个 x\in[1,n)，得知目标位置在 [1,x] 还是 (x,n]，发现可以递归到子问题。
于是，设 f(i,0/1) 表示：得知目标位置在 [1,i] 后，当前棋子在 1 或 i+1，的最小答案。
转移有：
f(i,0)\gets \min_{x=1}^{i-1} \{\max\{f(x,1),f(i-x,0)\}+w(x)\} \\
f(i,1)\gets \min_{x=1}^{i-1} \{\max\{f(x,0),f(i-x,1)\}+w(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 转移可以写为：
$$
f(i,0)\gets \min_{x=1}^{\min\{i-1,V\}} \{\max\{f(x,1),f(i-x,0)\}+w(x)\} \\
f(i,1)\gets \min_{x=1}^{\min\{i-1,V\}} \{\max\{f(x,0),f(i-x,1)\}+w(x)\}
$$
于是 $w(x)$ 的定义域被缩小到了 $O(V)$。总复杂度 $O(T(nV+mV))$，分别为 DP 和最短路的复杂度。
然后 $f$ 状态中的 $0/1$ 其实没什么用，可以直接记 $f(i)$，转移为：
$$
f(i)\gets \min_{x=1}^{\min\{i-1,V\}} \{\max\{f(x),f(i-x)\}+w(x)\}
$$