LCA 组合方法

组合问题的形式：通常有一个个体集合 $U$ ，以及形式方案集合 $V$ ，其每个元素都是个体集合的子集： $\forall v\in V,v\sube U$ 。

每种方案都有一个权值，在判定问题中是 $0/1$ ，在计数问题中通常是个体权值的和/积，在最优化问题中是各种不同的神秘定义。

组合问题中通常有“合法方案”这一概念，我们用判定函数 $I(A)$ 的值 true/false 来判断，称所有合法方案构成的集合是 $\mathcal I$ ，通常讨论的范畴是合法方案。

组合问题的分类：

通用的组合方法

在最优化问题中，可以直接规定不合法方案的权值是最劣的，此时变成了单纯的优化权值。

调整法：需要保证调整后仍然是合形式的（仍然是一种满足限制的方案），且调整后不劣于调整前。

输入序列 $h$ ，一张完全图上点 $i$ 和 $j$ 之间的边权是 $(h_i-h_j)^2$ ，求该图最小哈密顿回路。

$n\le 10^5$ 。

输入的东西只有一个序列，所以我们排序后在数轴上考虑这个问题。

首先我们找到形式方案集合：所有回路。

回路实在太多，考虑简化该集合，我们发现顺着走比绕着走好，更具体地：如果一段路起点是路径最小的，终点是路径最大的，那么最优方法就是排序访问。

你发现最小点到最大点满足这个条件，最大点到最小点同理，所以我们简化了“回路”：变成将中间的点划分为两个集合，上集合顺次访问，下集合逆序访问。

可以写出 $f_{i,j}$ 表示考虑了 $[1,\max(i,j)]$ 的所有点，上集合的最后一个点是 $i$ ，下集合最后一个点是 $j$ ，最小权值。

能否进一步优化？进一步地，我们发现交叉优于包含，即如果上集合的相邻点对对下集合的相邻点对形成了包含关系，那么我们可以交换靠后的点变成交叉关系，权值更优。

于是我们又简化了考虑集合：中间的点一定交替出现在上集合和下集合，这只有一个状态，可以直接算答案。

在判定/构造问题中，我们通常会仿照最优化的思路来实现简化问题。