P11693题解

Jadonyzx · 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)。

预处理即可。