题目地址：http://vjudge.net/problem/UVA-10795
参考自刘汝佳的思路
以下是个人理解：
普通的汉诺塔肯定都做过了，就是把一叠碟子放到另一根上
看到这个问题就很自然地想到普通的汉诺塔问题，于是也便想怎么转化成普通的汉诺塔问题：一堆放在另一堆上，需要2^(n-1)-1步
那么是不是可以定义一种中间状态，并且这个中间状态可以运用到普通汉诺塔，那么答案就是start->中间状态+final->中间状态
这个中间状态就是需要排的编号最大的盘子k，k要放到final柱子上，那么其他1~k-1盘子只能在除了k和final柱子的另一根记为other上
于是就需要算出start和final局面1~k-1盘子到other这柱子上的步骤，因为other这根柱子上排序是1~k-1的就像普通的汉诺塔一样，所以可以直接用结论2^(n-1)-1
另外，因为编号小的不能放在编号大的下面，所以我们应该从编号大的先开始排，那么排好后就不需要再考虑这个盘子了。比如，同时在拍k盘子时，比k大的肯定都放好了，他们也并不碍事，所以可以无视他们
#include <bits/stdc++.h>
using namespace std;
const int maxn=60+3;
typedef long long LL;
int start[maxn],final[maxn];
LL f(int* P,int i,int final){if(i==0) return 0;if(P[i]==final) return f(P,i-1,final); //i在final柱子上，不用排else return f(P,i-1,6-final-P[i])+(1LL<<(i-1)); //1~i-1到final需要2^(i-1)-1，加上移动i的步数
}
int main(int argc, char const *argv[])
{int n,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",&final[i]);int k=n;while(k>=1&&final[k]==start[k]) k--; //找不同柱子编号最大的一个LL ans=0;if(k>=1){int other=6-start[k]-final[k];ans=f(start,k-1,other)+f(final,k-1,other)+1;}printf("Case %d: %lld\n", ++kase,ans);}return 0;
}