自动搬运

查看原文

来自洛谷，原作者为

	Falashiro 丝之歌什么时候出

搬运于2025-08-24 23:07:40，当前版本为作者最后更新于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$。

则：

$$\begin{aligned} f(i,j)=\min\{&h_{u,L,0,i}+h_{u,R,0,j},h_{v,L,0,i}+h_{v,R,0,j},\\ &h_{u,L,1,i}+h_{v,R,1,j}-[u,v]_w,h_{v,L,1,i}+h_{u,R,1,j}-[u,v]_w\} \end{aligned} $$

于是我们以 $\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)$。