湯澤教案資料

從一類單調(diào)性問題看算法的優(yōu)化長沙市一中湯澤充分挖掘數(shù)據(jù)關(guān)系,靈活運(yùn)用數(shù)據(jù)結(jié)構(gòu),往往是構(gòu)造出優(yōu)秀算法的關(guān)鍵因素一般隊(duì)列:一端插入,另一端刪除特殊隊(duì)列:尾端插入,兩端刪除單調(diào)性:幫助優(yōu)化一類單調(diào)性問題問題1鋸木廠選址2<=N<=20000,1<=Wi<=10000,1<=Di<=10000123112112131261213W:N=9D:問題1鋸木廠選址最優(yōu)方案中,鋸木廠必定建在有樹的位置問題1鋸木廠選址分析:C[I]:在第I棵樹處建立一個鋸木廠,并且將第1到第I棵樹全部運(yùn)到這個鋸木廠所需的費(fèi)用W[J,I]:在第I棵樹處建立一個鋸木廠,并且將第J+1到第I棵樹全部運(yùn)往這個鋸木廠的費(fèi)用

問題1鋸木廠選址分析:F[I]表示在第I棵樹處建立第二個鋸木廠的最小費(fèi)用,則:這個算法的時(shí)間復(fù)雜度為O(N^2)問題1鋸木廠選址

I

JI+1

J問題1鋸木廠選址證明:令S[K,I]表示決策變量取K時(shí)F[I]的值

設(shè)K1<K2<I,S[K1,I]-S[K2,I]<0

問題1鋸木廠選址證明:設(shè)K1<K2<I,S[K1,I]-S[K2,I]<0令g[K1,K2]=上面不等式的左邊

因?yàn)镈[K]≥0,因此Sd序列不下降

因此決策是單調(diào)的!問題1鋸木廠選址分析:

維護(hù)一個特殊隊(duì)列K,K1<K2<…<Kn,g[K1,K2]<g[K2,K3]<…g[Kn-1,Kn]:計(jì)算狀態(tài)F[I]前,若g[K1,K2]<=Sd[I],表示決策K1不比K2優(yōu),刪除K1,重復(fù)該步驟問題1鋸木廠選址分析:計(jì)算F[I],F[I]=C[K1]+W[K1,I]+W[I,n+1]若g[Kn-1,Kn]>g[Kn,I],Sd[I’]>g[Kn-1,Kn]>g[Kn,I]Kn比Kn-1優(yōu)之前I就將比Kn優(yōu),刪除Kn,重復(fù)該步驟,最后將I插入隊(duì)列

算法總復(fù)雜度O(N)問題2旅行問題問題描述:一個環(huán)形跑道上有n個加油站，按順時(shí)針編號為1到n(3<n<10^6)第i號加油站有Pi(0<=Pi<10^9)升汽油,每升汽油可供行駛一千米第i號車站到其下一站的距離為Di(0<di<10^9)問題2旅行問題一個例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=43150512214問題2旅行問題一個例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4S=3S=3S=6S=4S=8S=2S=1S=4S=3S=4以1號加油站為起點(diǎn)問題2旅行問題一個例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4S=1以2號加油站為起點(diǎn)S=-1問題2旅行問題一個例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4S=1S=0S=-1以2號加油站為起點(diǎn)S=3問題2旅行問題一個例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4以1、3、5號加油站為起點(diǎn)有辦法周游一圈算法一分析:直接模擬剛剛的演算過程總的時(shí)間復(fù)雜度為O(N^2)

但是N最大可以達(dá)到10^6!太慢了!算法二分析:假定只能按順時(shí)針方向行駛.令A(yù)[I]=P[I]-D[I]A[I+N]=A[I]A[0]=0

設(shè)SA[I]表示A序列中前I項(xiàng)的和算法二0123456789A02-13-112-13-1sa021434658712345P31505D12214算法二分析:SA[I]到SA[I+N-1]都不小于SA[I-1]SA[I]到SA[I+N-1]中的最小數(shù)不小于SA[I-1]

求N個數(shù)中的最小數(shù),很自然地想到了堆!算法二0123456A02-13-112Sa021434612434134413464堆中不超過N個元素2N次插入操作2N次刪除操作N次取堆頂元素總復(fù)雜度O(NLog2N)算法三分析:給定一個序列SA和N個區(qū)間求出每個區(qū)間中的最小值,對其作相應(yīng)判定

這是一個標(biāo)準(zhǔn)的RMQ問題!時(shí)間復(fù)雜度降為O(N)SA:0214342143

算法四分析:

給定的N個區(qū)間不存在包含關(guān)系,滿足單調(diào)性!

0123456789Sa:0214342143

K:

22777同樣滿足單調(diào)性?算法四預(yù)處理:維護(hù)一個特殊隊(duì)列K,K1<K2<…<KnSa[k1]<Sa[k2]<…Sa[Kn]將1,2…n-1依次插入隊(duì)列K.插入前,如果Sa[i]<=Sa[kn],將Kn刪除.反復(fù)該步驟,最后將i插入隊(duì)列算法四求解并更新K:若K1=i-1,將K1刪除出隊(duì)列插入新位置號i+n-1,若Sa[Kn]>=Sa[i+n-1],刪除Kn,重復(fù)這個步驟,最后將i+n-1作為Kn插入隊(duì)列若Sa[k1]>=Sa[i-1],表示從i號加油站出發(fā)可以周游一周總復(fù)雜度O(N)四個算法比較空間復(fù)雜度時(shí)間復(fù)雜度實(shí)現(xiàn)難度算法一O(N)O(N^2)很容易算法二O(N)O(Nlog2N)