汉诺塔（二）
时间限制： 3000 ms | 内存限制：65535 KB
难度： 5
- 描述
-
汉诺塔的规则这里就不再多说了，详见题目：汉诺塔（一）
现在假设规定要把所有的金片移动到第三个针上，给你任意一种处于合法状态的汉诺塔，你能计算出从当前状态移动到目标状态所需要的最少步数吗？
- 输入
- 第一行输入一个整数N，表示测试数据的组数(0<N<20) 每组测试数据的第一行是一个整数m表示汉诺塔的层数(0<m<32)，随后的一行有m个整数Ai,表示第i小的金片所在的针的编号。（三根针的编号分别为1，2，3） 输出
- 输出从当前状态所所有的金片都移动到编号为3的针上所需要的最少总数 样例输入
-
231 1 131 1 3
样例输出 -
73
题解：把编号n移动到3号柱子需要2^(n-1); 1、总的来说一定是先把最大的盘子移到第三个柱子上， 然后再把第二大的移到柱子3上， 然后再把第三大的盘子移到柱子3上………直到把最小的盘子（1号盘子）移到柱子3上，才算结束。 2、现在设想一下，在移动第k个盘子动作前，柱子上的整体情况， 假设盘子k在柱子1上， 要移到柱子3上， 由于那些比k大的盘子都已经移动完了，就不需要考虑了。那么此时那些所有比k小的盘子都应该在柱子2上，因为他们不能在柱子1、3上，并且此时柱子2上的盘子从上到下盘子编号依次为1，2, 3…….k-1。 3、找出最大的盘子，先从最大的盘子开始移动， 如果最大的盘子已经在柱子3（目标柱子）上那就不用移动了。 所以我们应该找出不在柱子3上的最大盘子。 4、我们在这里先说一下这个函数ac（i, x）表示前i个盘子全部移到地x个柱子上所需的最少步数。那k个盘子（在柱子1上）举例：把盘子k移到柱子3上前一瞬间柱子上的情况是 ：1到k-1个盘子都在柱子2上， k在1上。ac（k-1, 2）就是移动到之一状态所需的步数。此时k移到柱子3需要1步。 要想把所有盘子移到3上，还需将2上 1~k-1 个盘子全部移到柱子3上。 思路就是从最大的编号开始往前找；当不在应该呆的编号上时就要移动到这个地方，则需要加上1<<(i-1); 代码：
#include#include #include #include using namespace std;const int INF=0x3f3f3f3f;#define mem(x) memset(x,0,sizeof(x))#define SI(x) scanf("%d",&x)#define SL(x) scanf("%lld",&x)#define PI(x) printf("%d",x)#define PL(x) printf("%lld",x)#define P_ printf(" ")#define T_T while(T--)const int MAXN=40;int a[MAXN];int ans;int main(){ int T,n; SI(T); T_T{ ans=0; SI(n); for(int i=1;i<=n;i++)SI(a[i]); int cur=3; for(int i=n;i>0;i--){ if(a[i]!=cur){ cur=6-a[i]-cur; ans+=1<<(i-1); } } printf("%d\n",ans); } return 0;}