图文网站建设,汽车营销服务网站建设,vr全景网站怎么做,企业门户网站设计论文项目编号#xff1a;bzoj-1019 项目等级#xff1a;Safe 项目描述#xff1a; 戳这里 特殊收容措施#xff1a; 对于一个hanoi#xff0c;知道了各种移动操作的优先级#xff0c;也就确定了方案。可以证明对于盘子数为N的hanoi#xff0c;任意移动方案都等价于将数目为N…项目编号bzoj-1019 项目等级Safe 项目描述 戳这里 特殊收容措施 对于一个hanoi知道了各种移动操作的优先级也就确定了方案。可以证明对于盘子数为N的hanoi任意移动方案都等价于将数目为N-1的一叠盘子移动k次并将最小的一个盘子经过b次后移动到目标柱顶端。这样hanoi的任一移动方案所需次数都满足线性递推式f[n]k*f[n-1]b。 因此我们暴力算出数列f的前几项更确切地前三项即可然后递推即可。加上矩乘优化后理论复杂度O(log2n)。 附录 嗯实际上N≤30根本不需要矩乘。。也懒得写。。 1 #include bits/stdc.h2 #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 stackint stick[3];
10
11 inline long long solve(const intx)
12 {
13 long long ret0; int las3;
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()xstick[2].size()x;ret)
17 {
18 range(i,0,6)
19 {
20 int fropt[i][0]-A,toopt[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[lasto].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 cinN; range(i,0,6) cinopt[i];
40 f[1]1,f[2]solve(2),f[3]solve(3);
41 long long k(f[3]-f[2])/(f[2]-1),bf[2]-k;
42 range(i,4,N1) f[i]k*f[i-1]b;
43 return coutf[N]endl,0;
44 } View Code 转载于:https://www.cnblogs.com/spactim/p/6934861.html
