poj1958 Strange Towers of Hanoi 题解报告

2023-09-09 阅读 25 评论 0

摘要：题目传送门【题目大意】有四个汗诺塔，$n$个盘子，求最小移动步数。【思路分析】对于三个汗诺塔的情况，设$f[i]$表示移动$i$个盘子所需的最小步数，当已经有$i-1$个盘子移动到位时，需要把这$i-1$个盘子先移开，把第$i$个盘子移动到

题目传送门

【题目大意】

有四个汗诺塔，$n$个盘子，求最小移动步数。

【思路分析】

对于三个汗诺塔的情况，设$f[i]$表示移动$i$个盘子所需的最小步数，当已经有$i-1$个盘子移动到位时，需要把这$i-1$个盘子先移开，把第$i$个盘子移动到位后在移回去，则有$$f[i]=2*f[i-1]+1$$

而对于四个汗诺塔的情况，设$ff[i]$表示最小移动步数，则有$$ff[i]=min\{2*ff[j]+f[i-j]\}(1\le j<i)$$

【代码实现】

 1 #include<iostream>
 2 #define rg register
 3 #define go(i,a,b) for(rg int i=a;i<=b;i++)
 4 using namespace std;
 5 int f[15],ff[15];
 6 const int INF=1e5;
 7 int main(){
 8     go(i,1,12) f[i]=ff[i]=INF;
 9     f[1]=ff[1]=1;
10     go(i,2,12) f[i]=f[i-1]*2+1;
11     go(i,2,12) go(j,1,i-1)
12         ff[i]=min(ff[i],2*ff[j]+f[i-j]);
13     go(i,1,12) cout<<ff[i]<<endl;
14     return 0;
15 }