双倍经验 ：Luogu P1242
分析
汉诺塔相信每一个合格的 OIer 都听说过并且实现过。这是一个递归的程序。
汉诺塔本来就有两个规则：
-
一次只能移动最上面的一个盘子。
-
编号大的盘子不能压在编号小的盘子上面。
汉诺塔问题给我们的结论就是下面这几句话：
把 \(n\) 个盘子的汉诺塔整体地从一根柱子移动到另一根柱子，
等价于把前 \(n-1\) 个盘子整体移动到中转柱子，
把第 \(n\) 个盘子移到那根柱子，把前 \(n-1\) 根柱子移动到那根柱子这三步加起来的和。
一句话：把 \(n\) 个盘子整体地移动到另一边，需要 \(2n - 1\) 步。证明就略过了。
所以新汉诺塔问题来了：已知初始盘子的状态和终止盘子的状态，求需要多少步才能转换。
我们是通过两个数组进行操作，一个叫 \(start\) 数组，表示初始状态每个盘子在哪根柱子上，即取值为 \([1,3]\)，另一个叫 \(finish\) 数组，相似的定义。
有一个小结论：当目前编号最大的不在目标柱子上的盘子，是必须移动的。这是首要的矛盾。
所以我们应该找出如此的盘子，然后把它上面的盘子都移走，同时那根柱子上的盘子也要相应的挪开给大盘子腾出空间。
对于 UVA10795，蓝书里面用了可逆性来进行递推，有兴趣的直接翻看蓝书的讲解。其实真的讲得很好。
\(Code\)
#include<cstdio>
const int maxn = 65;
int start[maxn], finish[maxn];
int n;
long long move(int *arr, int k, int to)
{
if(k == 0) return 0;
if(arr[k] == to) return move(arr, k - 1, to);
return move(arr, k - 1, 6 - arr[k] - to) + (1ll << (k - 1));// 这里本来有-1和+1，抵消了
}
int main()
{
int kase = 0;
while(scanf("%d", &n) == 1 && n)
{
for(int i = 1; i <= n; i++) scanf("%d", &start[i]);
for(int i = 1; i <= n; i++) scanf("%d", &finish[i]);
int k = n;
while(k >= 1 && start[k] == finish[k]) k--;
printf("Case %d: ", ++kase);
if(k >= 1)
{
printf("%lld\n", move(start, k - 1, 6 - start[k] - finish[k]) + move(finish, k - 1, 6 - start[k] - finish[k]) + 1);
}
else printf("0\n");
}
return 0;
}