[POJ1958]Strange Towers of Hanoi[递推,计数]

题面

这应该叫做Hanoi四塔问题, 规则同三塔问题. 可以从他们之间的联系着手.

先看3塔问题的递推求解: 设F3[n]为n盘3塔的步数, 要把n个盘从A移到C, 就要先把上面的n-1个盘从A移到B(借助C), 共F3[n-1]步, 再把第n个盘移到C, 1步, 最后把n-1个盘从B移到C(借助A), 也有F3[n-1]步. F[1]=1, 这样就很容易递推了.

设F4[n]为n盘4塔的步数. 最开始四根柱子依次为ABCD都可用, 要把所有盘从A移到D, 总要先移几个盘子到其他柱子上, 具体多少个我们不知道,设为k个, 即可以先在四塔问题中A->B移k个盘子, 共F4[k]步, 此时塔B的顶部已经放置了最小的盘, B柱不能再使用, 所以ACD就构成三塔问题, 把A柱上剩的盘移到D上共F3[n-k]步, 最后是B->D的四塔问题, 因为此时AC是空的, 可用, D上面的盘都比B上的盘大(一开始从A的顶部移来的), 也可用, 又有F4[k]步. 三者相加为k状态下的总步数. 枚举k取1~n-1, 取最小的答案即可.

#include<cstdio>
#include<cstring>
#define in inline
#define re register
#define int long long
in int read()
{
	int s(0),b(0);char ch;
	do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	if(b) return -s;
	return s;
}
in int min(int x,int y){if(x<y)return x;return y;}
int f3[20],f4[20];
signed main()
{
	memset(f4,0x3f3f3f3f,sizeof(f4));
	f3[1]=f4[1]=1;
	for(re int i=2;i<=12;++i) f3[i]=f3[i-1]*2+1;
	for(re int i=2;i<=12;++i)
		for(re int j=1;j<i;++j) f4[i]=min(f4[i],2*f4[j]+f3[i-j]);
	for(re int i=1;i<=12;++i) printf("%d\n",f4[i]);
	return 0;
}
赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址