2232D

一个变种的汉诺塔问题。

每个圆盘有一个限制 $a_i$，该圆盘可移动当且仅当其满足条件：在它上方的圆盘数量等于 $a_i$，而第 $i$ 个圆盘上面最多有 $i - 1$ 个圆盘，所以一旦 $a_i \geq i$，就无解。

令 $f(i)$ 为把 $i$ 个圆盘移动到目标柱的移动次数，使用数学归纳法来证明 $f(i)\leq 2^i-1$，首先 $f(1)=1$，成立。

注意 $f$ 一定是单调不降

现在假设对于 $k\in[1,i-1]$ 成立：

对于 $a_i=0$，就变成了经典的汉诺塔问题的情况，我们先把上面 $i - 1$ 个圆盘移动到辅助柱，再把第 $i$ 个圆盘移动到目标柱，再把 $i - 1$ 个圆盘从辅助柱移动到目标柱即可，此时 $f(i)=2f(i-1)+1\leq 2^i-1$。

对于 $a_i>0$，此时可以先把 $i - a_{i} - 1$ 个圆盘移动到辅助柱，此时把第 $i$ 个圆盘移动到目标柱，然后把 $i - a_i - 1$ 个圆盘移动回起始柱，最后把 $n - 1$ 个圆盘移动到目标柱，则此时 $f(i)=2f(i - a_{i}-1)+f(i - 1)+1\leq 2f(i-2)+f(i-1)+1 \leq 2^i-2 \leq 2^i - 1$，得证，可以在 $2^n$ 时间复杂度内解决。