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的概念最難應該在定狀態吧~~。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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);
}
}