必选的枚举优化+破环成链的均摊：杭电1237-1006

时限8s

1006 好多石头

拼凑题

首先我们可以尝试枚举两条直线的交点，我们试图把这个复杂度弄到 $O(n^2)$

因为每个点都必须用上，所以我们钦定前两个点必须选上，然后我们再随便枚举剩下两个点。

接下来我们把这4个点的顺序枚一枚即可。

好，上述过程我们已经有一个交点了，现在就是判断在这个交点的情况下是否有合法方案了。

我们先把数值相同的数合并，那现在每个点就有一个权值 $a_i$，代表这个数出现的次数。

然后我们对每个数，让其分别作截距和斜率，使其和在这种情况下所需要的另一个数连边。

我们得到的是由一堆环和一堆链组成的图。问题转化为，我们现在每次可以覆盖一条边，使两边节点的数值各减少1，有没有办法使 $a_i$ 清零。

链的情况是容易的，我们直接从前往后枚举即可。

环的情况我们考虑破环成链，然后预先枚举第一个点和最后一个点的匹配次数，接下来再跑一圈判断是否可行。

这个复杂度看起来会炸，但如果我们选取的第一个点是 $a_i$ 最小的点，那样子均摊下来复杂度就对了。

总复杂度 $O(n^3)$