题解：P11473 名字取好了吗

Falashiro · 2024-12-24 00:22:56 · 题解

先考虑如何对于所有 i 求出 f(1,i)。

以下约定 [x,y] 表示连接 x 号点和 y 号点的线段（这条线段不一定在原图上存在），若 [x,y] 在原图上存在，记 [x,y]_w 表示 [x,y] 的权值。

设 g_{l,r,0/1,0/1} 为满足以下条件的路径的最小代价：

• 从 1 号点出发。
• 到达过第 l 个点与第 r 个点。
• 第 l+1 个点到第 r-1 个点都没有被经过。(r=1 时，认为 r-1=n)
• 第三个参数为 0/1 表示目前在第 l/r 个点。
• 第四个参数为 0/1 表示到达当前所在点的线段到 [l,r] 之间有/没有其他以当前所在点为端点的线段（若路径只包含一个点，可认为该参数为 0）。

初始设 g_{1,1,0,0}=g_{1,1,1,0}=0。可按照上述状态设计写出状态转移方程（转移方式较多，且转移时需要注意是否需要加上三角形面积）。由于图上线段数量与 n 同级，故可以以 \Theta(n^2) 的复杂度完成 dp，从而对于所有 i 求出 f(1,i)。

接下来考虑分治。每条线段将凸包分为两个部分，我们找到按线段分割后两个部分点数最小值最大的线段，对于一个规模为 n 的问题，可以证明按找到的线段分割后，点数较少的部分的点数至少为 \lceil\frac{n}{3}\rceil+1。

具体证明过程如下：首先可以将凸包拉成一个正多边形，不改变线段间的相交关系，凸包被线段分为若干个三角形，找到包含正多边形外接圆的圆心的三角形（若圆心在线段上，则可以任选一个包含这条线段的三角形），该三角形的三条边所对的弧的长度均不超过外接圆周长的一半，这些弧上的点数之和为 n+3（有 3 个点被重复计算两次），最长的弧至少包含了 \lceil\frac{n+3}{3}\rceil=\lceil\frac{n}{3}\rceil+1 个点，按该弧所对应的线段分割，即可得到一个点数较小的部分的点数至少为 \lceil\frac{n}{3}\rceil+1 的分割方案。

于是我们可以按一条线段将凸包分割为两个凸包，使得点数较少的部分的点数至少为 \lceil\frac{n}{3}\rceil+1，点数较多的部分的点数至多为 n-\lceil\frac{n}{3}\rceil+1。

分割凸包后，我们记这两部分的点集为 L 和 R，分割凸包的线段为 [u,v]（u 和 v 同时在 L 和 R 中）。现在需要求满足 i\in L 且 j\in R 且 i,j\not\in\{u,v\} 的点对 (i,j) 对答案的贡献。设 h_{u/v,L/R,0/1,i} 表示以 u/v 为起点，只经过 L/R 中的点，不经过/经过 [u,v]，终点为 i 的最小代价。可以通过之前的 dp 以 \Theta(n^2) 的时间复杂度求出所需的 h。

则：

于是我们以 \Theta(n^2) 的时间复杂度求出了所有满足 i\in L 且 j\in R 且 i,j\not\in\{u,v\} 的点对 f(i,j)。接下来考虑递归计算求 L 内部和 R 内部的点对对答案的贡献。递归计算 L 部分的过程中，需要考虑从 u 到 v 可以经过 R 中的点，于是可以通过 h_{u,R,0,v} 来更新 [u,v] 的权值，但注意这需要与原权值分开记录，因为不直接通过 [u,v] 的路径可能会影响 L 部分纯净三角形面积的计算。对于递归计算 R 部分的过程同理。

总体时间复杂度 T(n)=T(\frac{2n}{3})+T(\frac{n}{3})+\Theta(n^2)，可计算得总体时间复杂度为 \Theta(n^2)。