

$4.$魔术球问题

题目

假设有n根柱子，现要按下述规则在这 $n$根柱子中依次放入编号为 $1，2，3，...$ 的球。

• 每次只能在某根柱子的最上面放球。

• 在同一根柱子中，任何 $2$个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 $n$ 根柱子上最多能放多少个球。例如，在 $4$ 根柱子上最多可放 $11$ 个球。

编程任务：

对于给定的 $n$ ，计算在 $n$ 根柱子上最多能放多少个球。

题解

这题需要用到上一题的解法。 首先考虑如果我们已经确定了球的个数，如何确定最少需要多少个柱子才能将他们全部放下，这个可以看成一个最小路径覆盖问题，我们对于每一个编号为 $i$ 的球，找到所有编号为 $j$ , $(j < i)$ 的球时两个球编号和为完全平方数，此时在图中由 $j$ 向 $i$ 连一条有向边。 显然当所有边连完后这个图一定为有向无环图，那么一个柱子上面放的所有球从下到上肯定是图中的一条路径，所以可以看成最小路径覆盖。 那么可以考虑枚举球的个数（或者你可能想二分），然后求最小路径覆盖数，覆盖数是随着球的个数增加而单调不递减的。 但是我们不能使用二分而应该使用枚举来做，因为如果二分的话每次二分都需要重新建图一遍，但是枚举每次加一个球只需要将连向它的边加进去然后继续在残量网络上跑就行了，复杂度会优于二分。 那么应该如何求出答案。 当我们的最小覆盖数(设为 $f$)第一次大于 $n$ 时，那么最多可以放的小球数为 $f-1$，然后按照路径打印答案即可。