题面

---

小小数学题

回忆一下汉诺塔的做法：

要把 $n$ 个盘从 $\rm A$ 移到 $\rm C$（$n>1$）。

用 $H(n)$ 表示移动 $n$ 个盘所需的最少次数。移动步骤为：

1. 移动上面的 $n-1$ 个盘（从 $\rm A$ 到 $\rm B$，需 $H(n-1)$ 步）；
2. 移动最下面那个盘（从 $\rm A$ 到 $\rm C$，需 $1$ 步）；
3. 移动 $n-1$ 个盘（从 $\rm A$ 到 $\rm C$，需 $H(n-1)$ 步）。

故 $H(n)=H(n-1)+1+H(n-1)=2H(n-1)+1$。

这个新汉诺塔怎么做呢。。

---

设 $f(i)=i个盘沿允许方向移一步(移到相邻柱)的最少步数$（如 $\rm A\to B$、$\rm B\to C$、$\rm C\to A$），
$g(i)=i个盘沿允许方向移两步(移到隔一柱)的最少步数$（如 $\rm A\to C$、$\rm B\to A$、$\rm C\to B$）。
边界是 $f(0)=g(0)=0$。
答案就是 $g(n)$。

最重要的递推：

求 $f(i)$（以从 $\rm A$ 到 $\rm B$ 为例）

1. 把上面 $i-1$ 个盘从 $\rm A$ 移到 $\rm C$（需 $g(i-1)$ 次）；
2. 把最大盘从 $\rm A$ 移到 $\rm B$（需 $1$ 次）；
3. 把上面 $i-1$ 个盘从 $\rm C$ 移到 $\rm B$（需 $g(i-1)$ 次）。

这样把 $i$ 个盘移到了相邻柱，共需 $2g(i-1)+1$ 次，即 $f(i)=2g(i-1)+1$ 。

求 $g(i)$（以从 $\rm A$ 到 $\rm C$ 为例）

1. 把上面 $i-1$ 个盘从 $\rm A$ 移到 $\rm C$（需 $g(i-1)$ 次）；
2. 把最大盘从 $\rm A$ 移到 $\rm B$（需 $1$ 次）；
3. 把上面 $i-1$ 个盘从 $\rm C$ 移到 $\rm A$（需 $f(i-1)$ 次）；
4. 把最大盘从 $\rm B$ 移到 $\rm C$（需 $1$ 次）；
5. 把上面 $i-1$ 个盘从 $\rm A$ 移到 $\rm C$（需 $g(i-1)$ 次）。

这样把 $i$ 个盘移到了隔一柱，共需 $[2g(i-1)+f(i-1)+2]$ 次，即 $g(i)=2g(i-1)+f(i-1)+2$。

递推公式：

$$\begin{cases} f(i)=2g(i-1)+1,\\ g(i)=2g(i-1)+f(i-1)+2. \end{cases}$$

程序：

#include <cstdio>
int main() {
    int n, f[25], g[25];
    *f = *g = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        f[i] = g[i - 1] << 1 | 1;
        g[i] = ((g[i - 1] + 1) << 1) + f[i - 1];
    }
    printf("%d", g[n]);
    return 0;
}

$$\rm EOF$$