自动搬运

查看原文

来自洛谷，原作者为

	Jadonyzx awmc

搬运于2025-08-24 23:09:33，当前版本为作者最后更新于2025-02-09 18:57:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先对于初始的点 $u$，先手若采取一种短浅的走法，直接走到最近的最大点，一定是可行的，而后手直接走回 $u$，这种策略在一开始的点值也算上的情况下是正确的，但如果 $u>\forall v \in edge_u$ 这种方法就不一定对了。

考虑另一种情况，不妨设过程为 $u\longrightarrow v\longrightarrow w$。

但是考虑到后手走到 $w$ 后，由于 $w$ 结算过了，那么他只需要反向进行先手的操作即可使答案不再更新，那么游戏一定在 $4$ 步以内结束。

不妨设 $dp_{i,j,k}$ 表示到达 $i$ 号点，还剩 $j$ 步，轮到 $k$ 走的结果，不妨设先手为 $1$，那么答案就是 $dp_{x,\min(k,4),1}$。

转移：$dp_{i,j,1}=\max_{v\in edge_i}\max(dp_{v,j-1,0},v)$，$dp_{i,j,0}=\min_{v\in edge_i}\max(dp_{v,j-1,1},v)$。

预处理即可。