項(xiàng)目編號(hào)：bzoj-1019

項(xiàng)目等級(jí)：Safe

項(xiàng)目描述：

　　戳這里

特殊收容措施：

　　對(duì)于一個(gè)hanoi，知道了各種移動(dòng)操作的優(yōu)先級(jí)，也就確定了方案。可以證明對(duì)于盤(pán)子數(shù)為N的hanoi，任意移動(dòng)方案都等價(jià)于將數(shù)目為N-1的一疊盤(pán)子移動(dòng)k次，并將最小的一個(gè)盤(pán)子經(jīng)過(guò)b次后移動(dòng)到目標(biāo)柱頂端。這樣，hanoi的任一移動(dòng)方案所需次數(shù)都滿(mǎn)足線性遞推式f[n]=k*f[n-1]+b。

　　因此我們暴力算出數(shù)列f的前幾項(xiàng)（更確切地，前三項(xiàng)即可），然后遞推即可。加上矩乘優(yōu)化后理論復(fù)雜度O(log₂n)。

附錄：

（嗯，實(shí)際上N≤30根本不需要矩乘。。也懶得寫(xiě)。。）

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 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/spactim/p/6934861.html

總結(jié)

以上是生活随笔為你收集整理的SCP-bzoj-1019的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。