hdu 2077 漢諾塔 IV

Problem Description 還記得漢諾塔III嗎？他的規則是這樣的：不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間杆或從中間移出)，也不允許大盤放到小盤的上面。xhd在想如果我們允許最大的盤子放到最上面會怎麼樣呢？（隻允許最大的放在最上面）當然最後需要的結果是盤子從小到大排在最右邊。

Input 輸入資料的第一行是一個資料T，表示有T組資料。

每組資料有一個正整數n(1 <= n <= 20)，表示有n個盤子。

Output 對于每組輸入資料，最少需要的擺放次數。

Sample Input

2
1
10
        

Sample Output

2
19684
        

#include <stdio.h>
///疊代
int main()
{
    __int64 dp[21] = {0,1};
    int i;
    for(i = 2; i < 21; ++i )
        dp[i] = 3 * dp[i-1] + 1;///從中間柱子移入移除
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&i);
        printf("%I64d\n",(dp[i-1] + 1)<<1);///最大盤可放上面
    }

    return 0;
}