nyoj89 漢諾塔（二），nyoj89漢諾塔
題目網址 ：http://acm.nyist.net/JudgeOnline/problem.php?pid=89
漢諾塔問題的經典結論：
把i個盤子從一個柱子整體移到另一個柱子最少需要步數是 2的i次方減一。那我們這個給定一個初始局面，求他到目標局面（全部移到第三個柱子上）需要的最少步數。怎麼辦呢！！ 分析：
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上。 又已知經典漢諾塔結論 移動k-1個盤子需要2的k-1次冪減一。 那麼也就得出總共需要步數為：ac(k-1, 2) + 1 + pow(2, k-1) - 1 = ac(k-1, 2) + pow(2, k-1);
![]()
#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
using namespace std;
long long ans, a[10000][5];
int t, n, mx, star[10000];
long long ac(int x, int t)
{
if(x == 1)
{
if(star[x] == t)
return 0;
else
return 1;
}
if(a[x][t] != -1) return a[x][t];
if(star[x] == t)//如果第x個盤子已經在目標柱子上了那就不移動了， 直接考慮移動下一個
a[x][t] = ac(x-1, t);
else
a[x][t] = ac(x-1, 6-t-star[x]) + pow(2, x-1);
//三個盤子編號總和6， 不能在目標柱t子上， 又不能和要移動的盤子x在一個柱子， 只能在6-t-satr[x]上
return a[x][t];
}
int main()
{
cin >> t;
while(t--)
{
memset(a, -1, sizeof(a));
scanf("%d", &n);
mx = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &star[i]);
if(i > mx && star[i] != 3)
mx = i;
}
if(mx == 0)
printf("0\n");
else if(mx == 1)
printf("1\n");
else if(mx > 1)
{
ans = ac(mx-1, 3-star[mx]);
ans += pow(2, mx-1);
printf("%ld\n", ans);
}
}
return 0;
}
View Code
