G4027 [GESP202609 四级] 新汉诺塔 题解

知识点：递推、状态设计、数学建模。

解题思路

设one[n]为顺方向跨一根柱的最少步数，two[n]为跨两根柱的最少步数。递推one[n]=2two[n-1]+1，two[n]=2two[n-1]+one[n-1]+2，答案取two[n]。

为什么正确

移动最大盘前后，小盘堆必须转移到唯一合法的辅助柱；分解后的转移分别对应这两个状态，且各子步骤的最优值可依次达到。

易错点

更新两状态前保留旧值；不能用普通汉诺塔2^n-1公式，方向限制改变了递推。

复杂度

时间O(n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    long long one=0,two=0;
    for(int i=1;i<=n;i++) {
        long long a=2*two+1,b=2*two+one+2;
        one=a;
        two=b;
    }
    cout<<two;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。