🤳🏻202609 GESP 4 级第 1 题

⭐**一句话：本题思维难度严重朝纲。**⭐

这题放给很多过了5级，6级（甚至7，8级）的学生来做，估计照样很难做出来。

📶原因分析

我分析了大约点原因：

1. 严重的思维定式
2. 确实难推

首先 汉诺塔三个字一出来，只要是学过递归汉诺塔的学生肯定是肾上腺素一起来，然后思考了一会，再次肾上腺素到达顶峰。“不对啊，这题怎么用递归写啊。”

是的，本题用常规思路去想，也就是写递归然后计次，会非常非常的麻烦。而思路一旦进入定式后就很难，并很不愿意出来了。

其次 本题确实难推，对状态的定义也是比较抽象的。有些题解直接给出了一条公式就 ok 了，其实这种很不好。

一般这种题是需要先综合考虑多个状态，然后递推叠加后形成的一个方程组。最后通过一些转化而成的化简公式。

类似的题有：(经典dp) I型 L型 铺盖2n_21 l型 方案数-CSDN博客 这是一道非常经典的题。但绝对不是一道一眼就能看出来的简单的题。

📶洛谷反馈

在洛谷现在标注的是普及-，但是很多人都要求要提升到黄题（普及），但是到目前为止还是没改。

B4579 GESP202609 四级 新汉诺塔 题解 - 洛谷专栏

🤳🏻参考代码

题面：B4579 GESP202609 四级 新汉诺塔 - 洛谷

洛谷题解：B4579 GESP202609 四级 新汉诺塔 - 洛谷

AC代码：R307583766 - 记录详情 - 洛谷

/**
 * https://www.luogu.com.cn/problem/B4579
 * B4579 [GESP202609 四级] 新汉诺塔
 *
 * 新汉诺塔，只有两种操作
 * 目的是让总体 A->C
 */
#include <bits/stdc++.h>
using namespace std;

using ll    = long long;
const int M = 10 + 20;

int main() {
    int n;
    cin >> n;

    /**
     * ①. 状态定义
     *
     * 1.(f) 移动到下一根柱子
     * 如：A->B，C->A
     * 2.(g) 移动到再下一根柱子
     * 如：A->C，B->A
     */

    /**
     * ②. 状态转移
     *
     * A->B (f)
     *     1. 小盘子必须先从 A 搬到 C，需要 g 次
     *     2. 然后最大盘从 A 到 B，用 1 次
     *     3. 最后小盘子从 C 搬到 B，沿箭头要经过 A，需要 g 次
     *     ================================================
     *     = g + 1 + g
     *     = 2g + 1
     *
     * A->C (g)
     *     1. 小盘子从 A 搬到 C，需要 g 次，让最大盘能够移动。
     *     2. 最大盘从 A 搬到 B，用 1 次。
     *     3. 小盘子从 C 搬到 A，需要 f 次，让柱子 C 空出来。
     *     4. 最大盘从 B 搬到 C，用 1 次。
     *     5. 小盘子从 A 搬到 C，需要 g 次，叠在最大盘上。
     *     ==============================================
     *     = g + 1 + f + 1 + g
     *     = 2g + f + 2
     */

    /**
     * ③ 边界条件
     *
     * 当汉诺塔一个物品都没有的时候
     * 即 n=0 则方案为 0
     *
     * 当 n=1 g[1] = 2
     * 当 n=2 g[2] = 7
     * 但这些都是可以通过状态转移方程转移过来的
     */

    // f 跳1步
    // g 跳2步
    ll f[M] = {};
    ll g[M] = {};
    for (int i = 1; i <= n; i += 1) {
        f[i] = 2 * g[i - 1] + 1;
        g[i] = 2 * g[i - 1] + f[i - 1] + 2;
    }
    cout << g[n] << endl;

    return 0;
}

🤳🏻END

我在搜这道题的一些相关资料的时候，意外发现一个讲解视频。这个视频的老师解说是根据 n=2,3 的情况去猜递推公式。然后就直接把公式打出来。这也是真牛逼，不会讲可以不会，还非要显得自己多咋样