2020牛客寒假算法基础集训营3 I-牛牛的汉诺塔（记忆化搜索）

题目大意

汉诺塔， 伪代码为

Function Hanoi(n,a,b,c)
    if n==1 then
        print(a+'->'+c)
    else
        Hanoi(n-1,a,c,b)
        print(a+'->'+c)
        Hanoi(n-1,b,a,c)
    end if
end Function 

统计以下信息：A->B,A->C,B->A,B->C,C->A,C->B的次数，以及所有移动的总步数。

分析

一开始硬生生找规律， 呜呜呜呜呜， 找的心态爆炸最后终于找出来了。最后会贴出我自己找的规律的代码。

这里介绍另一种方法， 记忆化搜索。 当我看到题解有记忆化搜索的字样时， 突然间恍然大悟， 想尝试着自己写一下但是失败了， 呜呜，看着std才写出来的。

普通递归时间复杂度太高， 本质原因就是重复搜索了好多。记忆化搜索就是想办法让重复搜索的次数减少， 具体详见百度。

如果你明白记忆化搜索了， 那就直接看代码就行了， 不明白的话， 那就再去学！

代码

记忆化搜索

#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
inline ll read() {
    ll res = 0; bool f = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
    while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
    return f ? (~ res  + 1) : res;
}
inline int _(char a, char b){
    if (a == 'a' && b == 'b') return 1;
    if (a == 'a' && b == 'c') return 2;
    if (a == 'b' && b == 'a') return 3;
    if (a == 'b' && b == 'c') return 4;
    if (a == 'c' && b == 'a') return 5;
    if (a == 'c' && b == 'b') return 6;
}
struct node{
    ll sum[7];
    node(){ms(sum, 0);};
    node operator + (const node & x)const{
        node tmp;
        for (int i = 1; i <= 6; ++i) tmp.sum[i] = sum[i] + x.sum[i];
        return tmp;
    }
    ll getsum(){
        ll tmp = 0;
        for (int i = 1; i <= 6; ++i) tmp += sum[i];
        return tmp;
    }
}ans;
using tu = tuple<int, char, char, char>;
map<tu, int>vis; //表示这个 组合(int, char, char, char) 是否已经搜索到.
map<tu, node>ma; // 储存这个组合下的 node值是多少
node Hanoi(int n, char a, char b, char c){ // 注意返回值是node, 这个太妙了
    tu p = make_tuple(n, a, b, c);
    if (vis[p]) return ma[p]; // 如果访问过这个元组, 直接return这个元组的值就行
    node tmp;
    if (n == 1) {
        tmp.sum[_(a, c)]++; // a c 这步++
        return tmp;
    }
    tmp = tmp + Hanoi(n - 1, a, c, b);
    tmp.sum[_(a, c)]++;
    tmp = tmp + Hanoi(n - 1, b, a, c);
    vis[p] = 1;
    return ma[p] = tmp;
}

int main(){
    int n = read();
    ans = Hanoi(n, 'a', 'b', 'c');
    printf("A->B:%lld\n",ans.sum[1]);
    printf("A->C:%lld\n",ans.sum[2]);
    printf("B->A:%lld\n",ans.sum[3]);
    printf("B->C:%lld\n",ans.sum[4]);
    printf("C->A:%lld\n",ans.sum[5]);
    printf("C->B:%lld\n",ans.sum[6]);
    printf("SUM:%lld\n", ans.getsum());
    return 0;
}

我自己找的规律， 找了一个多小时， 心态在爆炸的边缘疯狂试探。不过没什么参考价值。

#include <bits/stdc++.h>

#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

inline ll read() {
    ll res = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = 1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        res = (res << 3) + (res << 1) + ch - '0';
        ch = getchar();
    }
    return f ? (~res + 1) : res;
}

ll sum[7][100];

int main() {
    // B -> A  C -> B
    sum[3][1] = 0;
    sum[3][2] = 0;
    sum[3][3] = 1;
    sum[3][5] = 6;
    for (int i = 3; i <= 30; ++i) {
        sum[3][2 * i + 1] = sum[3][2 * i - 1] * 4 + i;
    }
    for (int i = 1; i <= 30; ++i)
        sum[3][i * 2] = sum[3][i * 2 - 1];

    // A -> B B -> C
    sum[1][1] = 0;
    sum[1][2] = 1;
    sum[1][3] = 1;
    sum[1][4] = 4;
    sum[1][6] = 15;
    sum[1][8] = 58;
    ll tmp = 4 * 4;
    for (int i = 3; i <= 30; ++i) {
        sum[1][2 * i] = tmp - sum[3][(i - 1) * 2];
        tmp *= 4;
    }
    for (int i = 1; i <= 30; ++i)
        sum[1][i * 2 + 1] = sum[1][i * 2];

    // A -> C
    sum[2][1] = 1;
    sum[2][2] = 1;
    sum[2][3] = 3;
    for (int i = 2; i <= 30; ++i) {
        sum[2][2 * i] = sum[2][2 * (i - 1)] * 4 - (2 * (i - 1) - 1);
    }
    for (int i = 2; i <= 30; ++i)
        sum[2][2 * i - 1] = sum[2][2 * i];

    // C -> A

    sum[5][1] = sum[5][2] = sum[5][3] = 0;
    sum[5][4] = sum[5][5] = 2;
    for (int i = 3; i <= 30; ++i)
        sum[5][i * 2] = sum[1][i * 2] - i;
    for (int i = 1; i <= 30; ++i)
        sum[5][2 * i + 1] = sum[5][2 * i];

    // 总步数
    sum[0][1] = 2;
    for (int i = 2; i <= 60; ++i) sum[0][i] = sum[0][i - 1] * 2;

    int n = read();

    printf("A->B:%lld\n"
           "A->C:%lld\n"
           "B->A:%lld\n"
           "B->C:%lld\n"
           "C->A:%lld\n"
           "C->B:%lld\n"
           "SUM:%lld\n", sum[1][n], sum[2][n], sum[3][n], sum[1][n], sum[5][n], sum[3][n], sum[0][n] - 1);

    return 0;
}

恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。