TIOJ::1119 . 複雜之河內塔問題

http://tioj.ck.tp.edu.tw/problems/1119

河內塔進階題，會有大小一樣的木塊出現，複雜度O(n)。

這題因為是北市賽題目，所以測資很小，但是其實這題應該可以做到10^6的。

題目就是你有一個三柱的河內塔，每個大小的木塊都有若干個，你要把他們從柱A移到柱C，順序不能改變。

這題一開始會以為是一般的河內塔，透過遞迴解題，但是有一點不同，就是將一群大小相同的木塊移動時，順序會反轉，必須多花步驟將其反轉回來，這也是這題敢叫複雜河內塔的原因XD。

所以我們定義兩個整數，代表
1.將河內塔移動並且反轉其中所有的同大小木塊順序
2.移動並且順序不變
兩種狀況。

於是，定義 A(i)為搬動第 i 層需要的次數，B(i)為搬動第 i 層並反轉的次數，D(i)為第i 層有幾個一樣大的木塊，每一層的定義是不同大小的木塊。

我們可以注意到 B<= A。

B(0 )就是 D(0)，A(0) 是 D(0) * 2 -1 ，為何要減一，很顯然搬動這層的過程中，最下面的那塊木頭沒必要多搬一次，細節可以自行思考。

B( n ) = B( n-1 ) *2 + D( n )，因為上面反轉兩次的搬動就不影響上面的順序，然後這層就讓他反過來吧~~。

A( n )比較麻煩，如果這層是 1 ，那轉移就跟 B一樣，如果不是1呢?
我們很顯然要把這一層搬兩次(D( n )* 2)，然後因為河內塔的規則，上面要搬三次，前兩次用反轉的次數 B(n-1) 就可以，但是第三次要用 A(n-1)，不然順序就亂掉了。

這樣就能知道答案囉！

這題DP的概念最難應該在定狀態吧~~。

#include <cstdio>
#define F(n) Fi(i,n)
#define Fi(i,n) for(int i=0;i<n;i++)
#define N 11
bool gin(int &a){
    char c;
    while(c=getchar(),c<'0'||c>'9')if(c==-1)return 0;
    a=c-'0';
    while(c=getchar(),c>='0'&&c<='9')a=a*10+c-'0';
    return 1;
}
int a,n,ans,nans;
int main(){
    while(gin(n)){
        gin(a);
        ans=a*2-1,nans=a;
        F(n-1){
            gin(a);
            if(a>1)ans=nans*2+ans+a*2;
            else ans=nans*2+a;
            nans=nans*2+a;
        }
        printf("%d\n",ans);
    }
}