大家都所熟知汉诺塔，它有3根柱子
大致题意 求在4根柱子的情况下的方案数
首先,在3根柱子时，有一个非常熟悉的公式
$f[i]=f[i-1]*2+1$
它是什么意思呢？？
设有$n$个，假设它们在$A$上，可以先将前$n-1$个从$A->B\ \ \ ans+=f[n-1]$ 再将剩下一个从$A->C\ \ \ \ ans++$ 最后再将$n-1$个从$A->C\ \ \ \ ans+=f[n-1]$
所以 $ans=2*f[n-1]+1$
但是，此题有4根柱子！！
所以，我们先预处理3跟柱子的方案数$a[i](1<=i<=12)$
我们假设要求转$i$个所需的方案数$f[i]$，可以先将$j(1<=j<i)$从$A->B$需要$f[j]$
再将$i-j$个通过$a,c,d$将$A->D$需要$a[i-j]$
再将$b$上的$i$个从$B->D$需要$f[j]$
所以最终答案就是$\displaystyle\min_{j=1}^{j<i}\ \ f[j]*2+a[i-j]$
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 const int M=20; 6 int a[M],b[M]; 7 int main(){ 8 const int N=15; 9 memset(b,0x3f3f3f,sizeof(b)); 10 b[1]=1; 11 for (int i=1;i<N;++i) a[i]=a[i-1]<<1|1; 12 for (int i=2;i<N;++i) 13 for (int j=1;j<i;++j) 14 b[i]=min(b[i],(b[j]<<1)+a[i-j]); 15 for (int i=1;i<=12;++i) 16 printf("%d\n",b[i]); 17 return 0; 18 }
但是，由于n只有12,所以这是一道打表好题啊
1 #include <cstdio> 2 const int a[13]={0,1,3,5,9,13,17,25,33,41,49,65,81}; 3 int main(){ 4 for (int i=1;i<=12;++i) 5 printf("%d\n",a[i]); 6 return 0; 7 }