首页 > 代码库 > bzoj1019题解
bzoj1019题解
【解题思路】
对于一个hanoi，知道了各种移动操作的优先级，也就确定了方案。可以证明对于盘子数为N的hanoi，任意移动方案都等价于将数目为N-1的一叠盘子移动k次，并将最小的一个盘子经过b次后移动到目标柱顶端。这样，hanoi的任一移动方案所需次数都满足线性递推式f[n]=k*f[n-1]+b。
因此我们暴力算出数列f的前几项（更确切地，前三项即可），然后递推即可。加上矩乘优化后理论复杂度O(log2n)。
【参考程序】
（嗯，实际上N≤30根本不需要矩乘。。也懒得写。。）
1 #include <bits/stdc++.h> 2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i) 4 using namespace std; 5 6 static int N; 7 long long f[35]; 8 string opt[6]; 9 stack<int> stick[3];10 11 inline long long solve(const int&x)12 {13 long long ret=0; int las=3;14 range(i,0,3) for(;!stick[i].empty();stick[i].pop());15 dange(i,x,0) stick[0].push(i);16 for(;stick[1].size()<x&&stick[2].size()<x;++ret)17 {18 range(i,0,6)19 {20 int fr=opt[i][0]-‘A‘,to=opt[i][1]-‘A‘;21 if(22 fr!=las&&!stick[fr].empty()&&(23 stick[to].empty()||24 stick[fr].top()<stick[to].top()25 )26 )27 {28 stick[las=to].push(stick[fr].top());29 stick[fr].pop(); break;30 }31 }32 }33 return ret;34 }35 36 int main()37 {38 ios::sync_with_stdio(0);39 cin>>N; range(i,0,6) cin>>opt[i];40 f[1]=1,f[2]=solve(2),f[3]=solve(3);41 long long k=(f[3]-f[2])/(f[2]-1),b=f[2]-k;42 range(i,4,N+1) f[i]=k*f[i-1]+b;43 return cout<<f[N]<<endl,0;44 }
bzoj1019题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。