[SHOI 2008] 汉诺塔

题目大意

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

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

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

1n301 \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) = 1trans(i,  1)trans(i, \; 1)则可以由读入得到。

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

trans(i,  j1)=atrans(i, \; j - 1) = a ,剩下的一个盘子为 b=3iab = 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;
}