描述
“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有4根柱子， 而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？ 为了编程方便，您只需要输出这个结果mod 10000的值。 格式
输入格式
一个正整数n。（<=50000） 输出格式
一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。 样例1
样例输入1
2 样例输出1
3 限制
来源
huyichen
分析: 经典hanoi塔问题上加了一个柱子,可以先打一个程序然后找规律.打表程序思路: 第一步:先将x个通过a,b,d移到c柱 第二步,将剩下的(n-x)通过a,b移至d柱 第三步,将c放在d上
打表Code
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<cstdlib> #include<queue> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int MOD=10000,MAXN=5e4+10; typedef long long ll; const ll INF=1e12+10; ll f[MAXN]; int n; ll quick_pow(int x,int y){ ll ans=1; for(int i=y;i;i>>=1){ if(i&1) ans*=x; x*=x; } return ans; } int main(){ scanf("%d",&n); f[1]=1; f[2]=3; fo(i,2,n) { f[i]=INF; fo(j,1,i-1) { f[i]=min(f[j]*2+quick_pow(2,(i-j))-1,f[i]); } } printf("%lld",f[n]%MOD); return 0; }AC code
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<cstdlib> #include<queue> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int MOD=10000,MAXN=5e4+10; typedef long long ll; const ll INF=1e12+10; ll f[MAXN]; int n; int main(){ scanf("%d",&n); f[1]=1;f[2]=3; int l=2,r=2,t=2; fo(i,2,n) { f[i]=(f[i-1]+l); if(r>1) r--; else{ l<<=1; t++; r=t; } } printf("%lld",f[n]%MOD); return 0; }