HDU 1207 漢諾塔II

Problem Description

經典的漢諾塔問題經常作為一個遞歸的經典例題存在。可能有人并不知道漢諾塔問題的典故。漢諾塔來源于印度傳說的一個故事，上帝創造世界時作了三根金剛石柱子，在一根柱子上從下往上按大小順序摞着64片黃金圓盤。上帝指令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一回隻能移動一個圓盤。有預言說，這件事完成時宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門至今仍在一刻不停地搬動着圓盤。恩，當然這個傳說并不可信，如今漢諾塔更多的是作為一個玩具存在。Gardon就收到了一個漢諾塔玩具作為生日禮物。 

　　Gardon是個怕麻煩的人（恩，就是愛偷懶的人），很顯然将64個圓盤逐一搬動直到所有的盤子都到達第三個柱子上很困難，是以Gardon決定作個小弊，他又找來了一根一模一樣的柱子，通過這個柱子來更快的把所有的盤子移到第三個柱子上。下面的問題就是：當Gardon在一次遊戲中使用了N個盤子時，他需要多少次移動才能把他們都移到第三個柱子上？很顯然，在沒有第四個柱子時，問題的解是2^N-1，但現在有了這個柱子的幫助，又該是多少呢？

Input

包含多組資料，每個資料一行，是盤子的數目N(1<=N<=64)。

Output

對于每組資料，輸出一個數，到達目标需要的最少的移動數。

Sample Input

1

3

12

Sample Output

1

5

81

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=65;
long long f[maxn],n,ans;

int main()
{
    f[1]=1;
    for (long long i=2;i<maxn;i++)
    {
        ans=-1;
        for (long long j=1,k;j<i;j++)
        {
            k=1;
            k<<=(i-j-1);
            k=k-1;
            k=k+k+1;
            if (ans<0) ans=2*f[j]+k;
            else ans=min(ans,2*f[j]+k);
        }
        f[i]=ans;
    }
    while (~scanf("%d",&n)) printf("%d\n",f[n]);
}