用 $A, B, C$ 分别表示汉诺塔问题中的三根柱子。

用两个字母描述一个操作，例如 AB 就是把柱子 $A$ 最上面圆盘挪动到柱子 $B$ 上。

我们为所有的 $6$ 种操作赋予一个优先级，并且利用以下规则进行游戏：

1. 选择一种操作，这种操作是所有合法操作中优先级最高的。
2. 本次操作需要移动的圆盘不是上一次操作移动的圆盘。

可以证明，上述策略一定能完成汉诺塔游戏。 计算给定操作优先级时将 $A$ 柱子上的 $n$ 个圆盘全部移动到另一根上所需的操作数。

题解

由于优先级的限制，不能像传统的汉诺塔问题一样解决，考虑DP。

设 $f(j, i)$ 表示将 $i$ 号柱子最上面的 $j$ 个盘子（不考虑下面的盘子），移动到编号为 $g(j, i)$ 的柱子上所需要的最小移动次数。

显然的，当 $j = 1$ 时，$g(j, i)$ 由题目给定的优先级确定。按照 $j$ 从小到大划分阶段，则 $j > 1$ 时 $g(j, i)$ 的值由前一阶段确定。

转移 $f(j, i)$ 时，考虑 $f(j - 1, i)$ 和 $g(j - 1, i)$。

记 $g(j - 1, i) = a$，则按照传统的汉诺塔问题的思路应该移动到除了柱子 $i$ 和柱子 $a$ 的另一根柱子，记作 $b$，而且有 $b = 3 - a - i$。

若 $g(j - 1, a) = b$，则我们需要做的只有将柱子 $i$ 上的第 $j$ 个盘子移动到 $b$ 上，然后把柱子 $a$ 上的 $j - 1$ 个柱子移动到柱子 $b$ 上。

此时对于 $f(j, i)$ 有：

而对于 $g(j, i)$ 有：

若 $g(j - 1, a) = i$，则此时的最优解决方案是先将第 $j$ 个盘子移动到 $b$ 上，再将柱子 $a$ 上的 $j$ 个盘子移动到第 $i$ 根柱子上，再将盘子 $j$ 移动到柱子 $a$ 上，最后将柱子 $i$ 上的 $j - 1$ 个盘子移动到柱子 $a$ 上。

此时对于 $f(j, i)$ 有：

对于 $g(j, i)$ 有：

对于这种奇怪的转移可以通过对于只移动一根柱子的特殊情况的思考来理解。

代码

#include <cstdio>
const int MAX_N = 30;
int g[MAX_N + 1][3];
long long f[MAX_N + 1][3];
int main() {
    int n;
    scanf("%d", &n);
    g[1][0] = g[1][1] = g[1][2] = -1;
    for (int i = 0; i < 6; i++) {
        char rule[4];
        scanf("%s", rule);
        int fr = rule[0] - 'A', to = rule[1] - 'A';
        if (g[1][fr] == -1) g[1][fr] = to; // Good to own a BRAIN..
    }
    f[1][0] = f[1][1] = f[1][2] = 1;
    for (int j = 2; j <= n; j++) {
        for (int i = 0; i < 3; i++) {
            const int a = g[j - 1][i], b = 3 - a - i;
            if (g[j - 1][a] == b) {
                f[j][i] = f[j - 1][i] + 1 + f[j - 1][a];
                g[j][i] = b;
            } else {
                f[j][i] = f[j - 1][i] + 1 + f[j - 1][a] + 1 + f[j - 1][i];
                g[j][i] = a;
            }
        }
    }
    printf("%lld\n", f[n][0]);
    return 0;
}