[SHOI 2008] 汉诺塔

发表于2017-05-08更新于2020-08-06

题目大意

给定一组移动盘子的优先顺序，在移动时，要满足一下几点：

  • 移动合法
  • 要移动的盘子不是上次移动过的
  • 该移动方案是目前满足以上两条中优先级最高的

求完成 nn 层汉诺塔的最小步数。

1⩽n⩽301 \leqslant n \leqslant 30

题目链接

【SHOI 2008】汉诺塔 - Luogu 4285

题解

总想到数学老师喜欢把它叫做「河内塔」。。。感觉莫名喜感。。。

递推。

记 f(i,  j)f(i, \; j) 表示起点柱子为 ii 、完成 jj 层汉诺塔时的答案，trans(i,  j)trans(i, \; j) 为起点柱子为 ii 、完成 jj 层汉诺塔后盘子被移动到了哪个柱子。

显然，f(i,  1)=1f(i, \; 1) = 1 ，trans(i,  1)trans(i, \; 1)则可以由读入得到。

考虑计算 f(i,  j)f(i, \; j) ，与正常汉诺塔一样，是把上 j−1j - 1 层移走，移动大盘子，再把那 j−1j - 1 层移过去。

记 trans(i,  j−1)=atrans(i, \; j - 1) = a ，剩下的一个盘子为 b=3−i−ab = 3 - i - a 。那么递推如下：

f(i, \; j) = \begin{cases} \begin{align} &f(i, \; j -1) + 1 + f(a, \; j - 1) \qquad trans(a, \; j - 1) = b \\ &f(i, \; j - 1) + 1 + f(a, \; j - 1) + 1 + f(i, \; j - 1) \qquad trans(a, \; j - 1) = i \end{align} \end{cases}

trans(i, \; j) = \begin{cases} \begin{align} &b \qquad trans(a, \; j - 1) = b \\ &a \qquad trans(a, \; j - 1) = i \end{align} \end{cases}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
const int MAXN = 35;
long long f[3][MAXN];
int trans[3][MAXN];
void dp(int n) {
    for (int i = 2; i <= n; i++) for (int j = 0; j < 3; j++) {
        int a = trans[j][i - 1], b = 3 - j - a;
        if (trans[a][i - 1] == b)
            trans[j][i] = b, f[j][i] = f[j][i - 1] + 1 + f[a][i - 1];
        if (trans[a][i - 1] == j)
            trans[j][i] = a, f[j][i] = f[j][i - 1] + 1 + f[a][i - 1] + 1 + f[j][i - 1];
    }
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < 6; i++) {
        static bool vis[6];
        char s[2];
        scanf("%s", s);
        int a = s[0] - 'A', b = s[1] - 'A';
        if (vis[a]) continue;
        vis[a] = true;
        f[a][1] = 1;
        trans[a][1] = b;
    }
    dp(n);
    printf("%lld\n", f[0][n]);
    return 0;
}