ACWing 96 奇怪的汉诺塔 题解

ACWing 96 奇怪的汉诺塔 题解

xiaoh 2020-7-7

题意

现将汉诺塔的三柱换位四柱。对于$n\in [1,12]$的每一个$n$求$n$阶汉诺塔的最小操作步数。

题解

不妨记汉诺塔的柱子依次为$A,B,C,D$，先回顾一下三柱汉诺塔的计算方法。我们先将$n-1$个盘子从$A$柱搬到$B$柱，然后将$n$号盘从$A$柱搬到$C$柱，再将$n-1$个盘子从$B$柱搬到$C$。所以递推式为$g_n=2g_{n-1}+1$.

而四柱汉诺塔既然多了一根柱子，我们更不能把它闲着。我们可以将$n-1$个盘子分成两部分，靠上面的一部分放到$B$柱,此时我们是按照“四柱”来计算的，剩下的由于有一部分已经占了一根柱子，所以我们只能在“三柱”模式下将剩余的一部分盘子放到$C$柱上，最后将$n$号盘子放到$D$柱上，最后再将两部分盘子分别从$B,C$移动到$D$上即可。所以递推式为$f_i=\max_{j=1}^{i-1}\{f_j+g_{i-j-1}\}$。按照上述递推式递推即可。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=15;
const long long inf=999999999;
long long f[MAXN];
long long g[MAXN];
int main()
{
    g[1]=1;
    for(int i=2;i<=12;++i) g[i]=g[i-1]*2+1;
    f[1]=1,f[2]=3;
    for(int i=3;i<=12;++i)
    {
        f[i]=inf;
        for(int j=1;j<i;++j) f[i]=min(f[i],2*f[j]+2*g[i-j-1]+1);
    }
    for(int i=1;i<=12;++i) cout<<f[i]<<endl;
	return 0;
}