P6742 [BalticOI 2014 Day2] Portals 题解补充

· · 题解

本题所有题解对于 使用传送门时发射两个门只用在同一个位置的最优性 都没有证明，均使用了显然或者直接给出这样的连边方式。

证明如下：

首先令一次传送过程的进入传送门的格子为入门 I，出口传送门的格子为出门 O。（格子指的是进入传送门前一步所在的格子）dis_{i,j} 表示不使用传送门时两个格子间的距离。

下面我们先证明上一次的入门 I_0 不会被再次使用：

  1. 若再次作为入门使用，那么假设我们在 P_1 处打出下一次的出门 O_1，那么再次使用 I_0 走到 O_1，从上一次进入 I_0 开始计算，时间为 1+dis_{O_0,P_1}+dis_{P_1,I_0}+1。
    若 dis_{O_0,P_1}<dis_{P_1,I_0}，那么考虑让 I_1=O_0，小于上述时间。
    若 dis_{P_1,I_0}\le dis_{O_0,P_1}，则不走前一次传送门，直接从 I_0 走到 P_1，打完 O_1 再走回来进入 I_0，小于上述时间。
  2. 若再次作为出门使用，由于 1，所以若再次使用上一次的 I，则一定都是作为出门使用。
    考虑第一个不作为出门使用的 I_n（最后一次传送的入门一定不作为出门使用），在此之前， I_i=O_{i+1}。
    因为 I_n\rightarrow O_n 之后，一定不会再次使用 I_n 及之前的传送门，所以可以直接考虑 I_1\rightarrow O_n 的路径可以直接省略为 I_1\rightarrow I_{n-1}=O_n 并直接走就行，显然比作为出门使用步数少。于是可以回溯到 I_0 也不作为出门使用。

再次证明上一次的出门不会用于下一次的出门：

由于不会重复使用入门，所以可以直接排除掉入门，发现两次状态相同，后面一次的传送是不必要的。

同时如果上一次的出门作为下一次的入门，那么可以直接假设原先就没有上一次的出门，重新发射一扇入门即可。

至此，我们证明了每两次传送间不会有影响（即上一次的传送门不会干扰下一次的传送）。这部分实际上是比较显然的，但是还是使用了较为严谨的方式证明。（如果有更简单的方法欢迎告诉笔者）

那么对于每次传送，我们钦定入门的发射一定在进入入门前的一个格子，那么对于发射出门的点 P_0，我们肯定是将入点选定在距离 P_0 最近的墙的位置。传送到 O_0 的时间为 dis_{P_0,I_0}。

接下来我们对于每次传送证明两次发射在同一个位置发射一定是最优的。（也就是各个题解中说的 I_0 在 P_0 四个方向上最短的墙的距离）

考虑 I_0 所在的墙 W_0（即 I_0 发射的传送门墙面所在的墙，和 I_0 不同）和 P_0 围成的长方形中一定不存在别的墙（若存在，则最优不为 I_0），那么这个长方形中一定有一个顶点可以同时看到 W_0 和 O_0，选择这个点发射传送门即可。