凸完全單調(diào)性的一個(gè)加強(qiáng)與應(yīng)用

凸完全單調(diào)性的一個(gè)加強(qiáng)與應(yīng)用第一頁(yè)，共四十一頁(yè)，編輯于2023年，星期二四邊形不等式、凸完全單調(diào)性與決策單調(diào)性以及凸完全單調(diào)性的一個(gè)加強(qiáng)第一部分第二頁(yè)，共四十一頁(yè)，編輯于2023年，星期二四邊形不等式、凸完全單調(diào)性與決策單調(diào)性

對(duì)于一個(gè)權(quán)函數(shù)w(i,j)，如果它滿足w(x,i+1)-

w(x,i)隨x單調(diào)不增，亦即w(x,i+1)+w(x+1,i)≥w(x,i)+w(x+1,i+1)，則稱這個(gè)權(quán)函數(shù)滿足凸完全單調(diào)性。容易證明，當(dāng)k>0時(shí)，w(x,i+k)-

w(x,i)隨x單調(diào)不減，w(i+k,x)-

w(i,x)隨x單調(diào)不減。所以對(duì)任意的a

b

c

d，有w(a,d)+w(b,c)

w(a,c)+w(b,d)。稱此不等式為四邊形不等式。由四邊形不等式也可推出凸完全單調(diào)性，所以“w滿足四邊形不等式”與“w具有凸完全單調(diào)性”這兩種說(shuō)法是等價(jià)的。第三頁(yè)，共四十一頁(yè)，編輯于2023年，星期二四邊形不等式、凸完全單調(diào)性與決策單調(diào)性

在一類要求將一段序列劃分為若干子段，從i到j(luò)的一段的費(fèi)用為w(i,j)，要求出所有子段代價(jià)之和最小的劃分方案的動(dòng)態(tài)規(guī)劃問(wèn)題中，通?？梢砸?jiàn)到這樣的狀態(tài)轉(zhuǎn)移方程：設(shè)t(i,x)=f[i]+w(i,x)，如果對(duì)于某個(gè)x，t(i,x)

t(j,x)(i<j)，則對(duì)于任何y>x，有t(i,y)

t(j,y)。此式說(shuō)明，對(duì)于i<j，一旦某個(gè)時(shí)刻決策i沒(méi)有決策j好，以后決策i也不會(huì)比決策j好。這說(shuō)明，f[x]的決策是隨x單調(diào)不減的，這就是決策的單調(diào)性。第四頁(yè)，共四十一頁(yè)，編輯于2023年，星期二四邊形不等式、凸完全單調(diào)性與決策單調(diào)性

解決這類問(wèn)題時(shí)，通常用B[i]記錄使決策i比所有之前的決策j(j<i)要好的最小的x，即B[i]=min{x:t(i,x)<t(j,x)對(duì)所有j<i均成立}。根據(jù)決策的單調(diào)性，決策i比所有之前的決策j(j<i)要好等價(jià)于B[i]

x。如果對(duì)某個(gè)(i,j)(i<j)，B[i]

B[j]，則說(shuō)明決策i是無(wú)用的。于是任何時(shí)刻，假設(shè)所有有用決策為i1,i2,…,ik，滿足i1<i2<···<ik，則B[i1]<B[i2]<···<B[ik]。第五頁(yè)，共四十一頁(yè)，編輯于2023年，星期二四邊形不等式、凸完全單調(diào)性與決策單調(diào)性

求解f[x]時(shí)，如果j=max{j:B[ij]

x,j

k}，則此時(shí)決策ij一定是最好的，即f[x]=t(ij,x)。利用決策的單調(diào)性，這個(gè)j可以接著上次查找，所以n次找j的時(shí)間復(fù)雜度為O(n+決策序列長(zhǎng)度)=O(n)。在求出了f[x]之后，x將成為一個(gè)有用決策，我們需要求出B[x]，以及維護(hù)這個(gè)決策序列。第六頁(yè)，共四十一頁(yè)，編輯于2023年，星期二四邊形不等式、凸完全單調(diào)性與決策單調(diào)性

假設(shè)可以在T單位時(shí)間內(nèi)求出y=min{y:t(x,y)<t(ik,y)}。那么如果y

B[ik]，一定有B[x]

B[ik]。于是ik是無(wú)用決策，這時(shí)應(yīng)當(dāng)在決策序列中刪去這個(gè)ik（只需要讓k←k-1）。繼續(xù)這個(gè)過(guò)程，直到min{y:t(x,y)<t(ik,y)}>B[ik]。此時(shí)，B[x]=y（因?yàn)椴豢赡茉傩。?，并且x應(yīng)當(dāng)被添加到這個(gè)決策序列的末尾。容易發(fā)現(xiàn)，用棧可以很好的完成這個(gè)序列的維護(hù)，由于每個(gè)決策至多進(jìn)出棧一次，每個(gè)決策出棧至多消耗T單位時(shí)間，于是維護(hù)序列的時(shí)間復(fù)雜度是O(nT)。又因?yàn)闆Q策的單調(diào)性，查找合適決策的時(shí)間復(fù)雜度是O(n)的，所以總的時(shí)間復(fù)雜度是O(nT)。第七頁(yè)，共四十一頁(yè)，編輯于2023年，星期二四邊形不等式、凸完全單調(diào)性與決策單調(diào)性

有時(shí)，因?yàn)楹瘮?shù)w的表達(dá)式便于求出min{y:t(x,y)<t(ik,y)}，所以T=O(1)；一般情況下，根據(jù)w的凸性可以得到t(x,y)-

t(ik,y)關(guān)于y單調(diào)不增，于是可以在O(logn)時(shí)間內(nèi)用二分的方法求出y，此時(shí)T=O(logn)。所以如果函數(shù)w是凸的，那么這種動(dòng)態(tài)規(guī)劃問(wèn)題最壞可以在O(nlogn)時(shí)間內(nèi)求解；最好時(shí)，可以在O(n)時(shí)間內(nèi)求解，可見(jiàn)這種方法是非常高效的。然而，此種動(dòng)態(tài)規(guī)劃模型單一，對(duì)w的限制有時(shí)又難以滿足，所以應(yīng)用范圍也較為狹窄。但其思想是值得借鑒的。第八頁(yè)，共四十一頁(yè)，編輯于2023年，星期二凸完全單調(diào)性的一個(gè)加強(qiáng)假設(shè)我們要維護(hù)一個(gè)廣義（不局限于動(dòng)態(tài)規(guī)劃問(wèn)題）決策序列i1,i2,…,ik，滿足i1<i2<···<ik，存在函數(shù)g和h，滿足在選取有關(guān)x的最優(yōu)決策時(shí)，決策i不如決策j(i<j)等價(jià)于g(i,j)

h(x)。此時(shí)，決策仍然具有單調(diào)性，不過(guò)這不是關(guān)于x單調(diào)，而是關(guān)于h(x)單調(diào)。類比上面的知識(shí)，容易知道，這里維護(hù)的決策序列滿足為了方便，我們記i0=nil。則g(ik

-1,ik)<g(ik,ik+1)。第九頁(yè)，共四十一頁(yè)，編輯于2023年，星期二凸完全單調(diào)性的一個(gè)加強(qiáng)我們需要在這個(gè)序列上進(jìn)行查找最小的j，滿足h(x)<g(ij,ij

+1)。還需要在適當(dāng)?shù)臅r(shí)候添加一個(gè)候選決策。函數(shù)g,h的出現(xiàn)，使這個(gè)方法有了更大的彈性，所以這個(gè)決策序列的維護(hù)方法也多種多樣，這些維護(hù)方法將在下一節(jié)中討論。在第一節(jié)介紹的w凸的一類動(dòng)態(tài)規(guī)劃問(wèn)題中，讓h(x)=x，容易證明g(ik

-1,ik)=B[ik]，此方法就退化為第一節(jié)所講方法。所以，利用凸完全單調(diào)性維護(hù)決策只是本方法的一個(gè)特例。第十頁(yè)，共四十一頁(yè)，編輯于2023年，星期二對(duì)此加強(qiáng)的進(jìn)一步分析第二部分第十一頁(yè)，共四十一頁(yè)，編輯于2023年，星期二選取適當(dāng)?shù)膆(x)加速算法例1(CEOI’2004TwoSawmills)在一座山上分布著N(2≤N≤10000)棵樹(shù)，由高到低依次編號(hào)為1,2,...,N。在山腳處還有一個(gè)伐木場(chǎng)。這N棵樹(shù)要被運(yùn)往伐木場(chǎng)進(jìn)行生產(chǎn)。每棵樹(shù)只能從高處運(yùn)往低處，而且這些樹(shù)都分布在一條路旁。第i棵樹(shù)的重量為Wi，它距離最山腳處的伐木場(chǎng)的距離為Pi。運(yùn)送每棵樹(shù)的代價(jià)為它的重量與它到伐木場(chǎng)的距離的乘積。總代價(jià)為運(yùn)送每棵樹(shù)的代價(jià)之和。伐木場(chǎng)的領(lǐng)導(dǎo)為了降低成本，決定在這條路旁的某兩個(gè)位置再建兩個(gè)伐木場(chǎng)。每棵樹(shù)被運(yùn)往不在它上方且離它最近的伐木場(chǎng)?，F(xiàn)在要確定這兩個(gè)新伐木場(chǎng)的位置，使得新的總代價(jià)最小，要求輸出最小總代價(jià)。第十二頁(yè)，共四十一頁(yè)，編輯于2023年，星期二選取適當(dāng)?shù)膆(x)加速算法我們直接解決新建k個(gè)伐木場(chǎng)的問(wèn)題。設(shè)

，

，d[k,i]表示從i到n建造k個(gè)伐木場(chǎng)的最小總代價(jià)。則本題的答案就是d[k,1]。由于d[k]只與d[k?1]有關(guān)，我們根據(jù)k來(lái)劃分階段。假設(shè)Ui

=d[k?1,i]?Ti

+Pi?1Si，則第十三頁(yè)，共四十一頁(yè)，編輯于2023年，星期二選取適當(dāng)?shù)膆(x)加速算法容易發(fā)現(xiàn)，這里的權(quán)函數(shù)是凸的，但是直接利用第一節(jié)的方法只能得到O(knlogn)的算法。利用第二節(jié)的方法可得，在計(jì)算d[k,x]時(shí)所以令，h(x)=Sx。假設(shè)此時(shí)的決策序列為i1,i2,…,ik，i1

>i2

>···>il，g(i0,i1)<g(i1,i2)<···<g(il?1,il)。第十四頁(yè)，共四十一頁(yè)，編輯于2023年，星期二選取適當(dāng)?shù)膆(x)加速算法在計(jì)算d[k,x]時(shí)，需要找到最小的j，滿足g(ij,ij+1)>Sx，則

。由于Sx在的計(jì)算過(guò)程中是單調(diào)增的（按照x從大到小的順序計(jì)算），我們只需要接著上次向后查找，于是這n次查找的總時(shí)間復(fù)雜度為O(n)。計(jì)算出d[k]之后，我們需要建立一個(gè)決策序列供下一階段選擇。我們按照從大到小的順序?qū)⑦@些候選決策加入決策序列。假設(shè)某個(gè)時(shí)刻決策序列為i1,i2,…,ik，i1

>i2

>···>il，此時(shí)要將x(il>x)添加到?jīng)Q策序列中。我們比較g(il?1,il)與g(il,x)的大小，如果g(il,x)g(il?1,il)，就刪去決策il（令l←l?1），繼續(xù)這樣的比較直到g(il?1,il)>g(il,x)，最后再將x放到?jīng)Q策序列的末尾。第十五頁(yè)，共四十一頁(yè)，編輯于2023年，星期二選取適當(dāng)?shù)膆(x)加速算法容易看出，這是一個(gè)棧維護(hù)的問(wèn)題。因?yàn)間的計(jì)算是O(1)的，所以整個(gè)過(guò)程的時(shí)間復(fù)雜度是O(n)。綜上，每個(gè)階段的計(jì)算是O(n)的，一共有k個(gè)階段，故總的時(shí)間復(fù)雜度為O(kn)。對(duì)比這個(gè)方法與直接利用凸完全單調(diào)性的方法可以發(fā)現(xiàn)，直接利用凸完全單調(diào)性的方法實(shí)際上是在求出了g(i,j)之后，用二分的方法求出了最小的滿足g(i,j)

Sx的x。而這是完全沒(méi)有必要的。如果w本身是凸的，通過(guò)選擇合適的h(x)（這里h(x)=Sx），那么這個(gè)h(x)與x一定具有相同的單調(diào)性，這不會(huì)影響查找的總時(shí)間，而計(jì)算g的復(fù)雜度由O(logn)降到了O(1)，這就將維護(hù)決策序列時(shí)間復(fù)雜度從O(nlogn)降到了O(n)，從而提高的算法的效率。第十六頁(yè)，共四十一頁(yè)，編輯于2023年，星期二用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問(wèn)題

在剛才的例題中，這個(gè)方法只是扮演著優(yōu)化的角色，并沒(méi)有質(zhì)的改變。下面，我們將利用這個(gè)方法解決一個(gè)權(quán)函數(shù)不滿足四邊形不等式的題目。例2(石階)水平面上有個(gè)高度為h的高臺(tái)，你需要用n(n≤1000)塊石塊修建一個(gè)石階，從這個(gè)高臺(tái)通往地面。第i個(gè)石階的高度為hi。由于一些限制，你從高臺(tái)出發(fā)，并且只能順次處理每塊石塊，你要么將當(dāng)前的石塊摞在你前方的那一列，要么走到前方的那一列。在修建石階的過(guò)程中你不能向回走。為了讓這個(gè)石階不至于太單調(diào)，你希望這個(gè)石階有所起伏，所以你希望將這n個(gè)石塊都用上。為了讓這個(gè)石階安全可用，你希望相鄰兩列高度之差的最大值（視高臺(tái)為第0列，地面為最后一列）盡可能小。也就是說(shuō)，你需要將這n個(gè)石塊分成若干段，假設(shè)你將他們分成了k段，則每段的高度為這段所有石塊的高度總和。假設(shè)第i段的高度為ti，t0=h，tk+1=0。你的目標(biāo)就是選擇一個(gè)合適的分段，來(lái)最小化。第十七頁(yè)，共四十一頁(yè)，編輯于2023年，星期二用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問(wèn)題

設(shè)h0=h,hn+1=0,d[k,x]為將石塊0到石塊x分成若干段，最后一段為石塊k到石塊x的方案中，相鄰兩段高度差的最小值。設(shè)si

=h0+···+hi，diff[i,k,x]=|sx?2sk?1+si?1|，則d[n+1,n+1]就是所求答案。第十八頁(yè)，共四十一頁(yè)，編輯于2023年，星期二用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問(wèn)題

這里，我們按照k從小到大,x從小到大的順序計(jì)算d[k,x]。我們需要維護(hù)n+1個(gè)決策序列，第k個(gè)決策序列存儲(chǔ)d[i,k?1]，其中i作為決策量。我們考察決策i比決策j更好的條件，以確定決策序列的各決策的序以及維護(hù)方法。設(shè)h(x)=sx?2sk?1，則決策i比決策j(i>j)好等價(jià)于第十九頁(yè)，共四十一頁(yè)，編輯于2023年，星期二用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問(wèn)題

容易發(fā)現(xiàn)，如果h(x)足夠大，那么此式一定不成立。我們考察這類不等式的解集。考慮函數(shù)f1(x)=max(|x+a1|,b1)，f2(x)=max(|x+a2|,b2)。這里a1

>a2，但b1、b2間沒(méi)有必然的大小關(guān)系。則這兩個(gè)函數(shù)間可能有以下幾種關(guān)系：第二十頁(yè)，共四十一頁(yè)，編輯于2023年，星期二用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問(wèn)題

第二十一頁(yè)，共四十一頁(yè)，編輯于2023年，星期二用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問(wèn)題

在圖中我們可以看到，f1(x)f2(x)的解集一定是xg(a2,b2,a1,b1)。故決策i比決策j(i>j)好等價(jià)于簡(jiǎn)寫(xiě)為h(x)g(j,i)。這里g是可以在O(1)時(shí)間內(nèi)求出的。第二十二頁(yè)，共四十一頁(yè)，編輯于2023年，星期二用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問(wèn)題

所以我們維護(hù)的每個(gè)決策序列中的決策應(yīng)當(dāng)滿足：查找決策時(shí)，應(yīng)當(dāng)找到最大的j，滿足h(x)g(ij?1,ij)。因?yàn)閔(x)=sx?2sk?1關(guān)于x單調(diào)增，我們可以接著上次向前查找，所以總的查找時(shí)間為O(n)。維護(hù)序列時(shí)，由于d[k,x]是按照k從小到大計(jì)算的，新的決策一定是被追加到?jīng)Q策序列的末尾，所以只需要反復(fù)比較g(il?1,il)與g(il,k)，刪去序列的末尾決策直到滿足g(il?1,il)>g(il,k)，最后將k追加到?jīng)Q策序列的末尾。第二十三頁(yè)，共四十一頁(yè)，編輯于2023年，星期二用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問(wèn)題

這樣，我們就得到了這個(gè)題目的O(n2)時(shí)間復(fù)雜度的解法。這個(gè)題目中，f2(x)-

f1(x)并不一定是單調(diào)增的，也就是權(quán)函數(shù)并不具有凸完全單調(diào)性，但我們還是利用這個(gè)方法解決了這個(gè)問(wèn)題。其原因在于，我們利用的只是決策的單調(diào)性，并不需要在意是哪個(gè)具體的性質(zhì)造成的這種單調(diào)性。對(duì)權(quán)函數(shù)要求過(guò)高，這便是凸完全單調(diào)性的局限，為一個(gè)不難達(dá)到的目的付出了過(guò)多的代價(jià)。第二十四頁(yè)，共四十一頁(yè)，編輯于2023年，星期二合理的序與維護(hù)方向

上面兩個(gè)例子，尤其是例2，向我們展示了這種方法的靈活性。動(dòng)態(tài)規(guī)劃的方程并不像第一節(jié)中的那么死板，也并不只有一個(gè)決策序列，決策的添加順序也沒(méi)有固定的要求。一個(gè)決策甚至可以被加入多個(gè)決策序列?。ǖ荒芴?，否則就與動(dòng)態(tài)規(guī)劃的本質(zhì)與維護(hù)決策的最終目的背道而馳；當(dāng)然，在例2中并未出現(xiàn)此情況）然而，解決動(dòng)態(tài)規(guī)劃問(wèn)題只是此類方法的一部分，此類方法還可以解決更為寬泛的問(wèn)題。第二十五頁(yè)，共四十一頁(yè)，編輯于2023年，星期二合理的序與維護(hù)方向

例3

(經(jīng)典問(wèn)題)

要求維護(hù)一些不與y軸平行的直線，為了方便，初始時(shí)只有一條直線y=∞。每次要么添加一條直線y=kx+b，要么詢問(wèn)x=k與這些直線的最低交點(diǎn)的坐標(biāo)。假設(shè)詢問(wèn)的次數(shù)為q，直線的條數(shù)為n，請(qǐng)給出一個(gè)O((n+q)logn)的算法。假設(shè)第i條直線為y=kix+bi?？紤]何時(shí)直線i不如直線j好。顯然，這等價(jià)于

但由于ki

-

kj的正負(fù)不確定，所以無(wú)法繼續(xù)變形下去。第二十六頁(yè)，共四十一頁(yè)，編輯于2023年，星期二合理的序與維護(hù)方向

回顧決策序列的維護(hù)過(guò)程，可以發(fā)現(xiàn)，此方法并沒(méi)有對(duì)決策的順序作任何顯式的要求，只要求決策滿足：回顧前兩個(gè)例題可以發(fā)現(xiàn)，決策的順序恰恰是暗含在函數(shù)g中的。第二十七頁(yè)，共四十一頁(yè)，編輯于2023年，星期二合理的序與維護(hù)方向

在本題中為了得到g(i,j)

h(x)，我們可以要求ki

kj。這樣就得到了一個(gè)合適的序。有了這個(gè)序，我們就可以得到：

即h(x)=x，第二十八頁(yè)，共四十一頁(yè)，編輯于2023年，星期二合理的序與維護(hù)方向

假如我們維護(hù)了一個(gè)決策序列i1,i2,…,il，滿足ki_1<ki_2<···<ki_l，-∞=g(nil,ki_1)<g(ki_1,ki_2)<···<g(ki_(l-1),ki_l)回答詢問(wèn)時(shí)，只要在這個(gè)序列中找最大的j，滿足g(ij-1,ij)

x。則所求交點(diǎn)一定在直線ij上。插入新直線時(shí)，由于這條直線并不一定是斜率最小的直線，所以我們不能在決策序列的末尾添加這個(gè)決策，而是要根據(jù)這條直線的斜率來(lái)決定是在開(kāi)頭還是中間還是末尾來(lái)維護(hù)這個(gè)序列。為了使算法描述盡可能地簡(jiǎn)潔，我們視序列的開(kāi)頭和結(jié)尾為一種退化了的中間。假設(shè)ki_j<kn

ki_(j-1)，我們可以用類似棧維護(hù)的方法刪去前面不需要保留的決策。假設(shè)這個(gè)時(shí)候n前方的決策變成了ij'，我們比較g(ij',x)與g(x,ij+1)來(lái)判斷決策n是否需要保留。如果需要保留，這時(shí)有可能g(n,ij+1)

g(ij+1,ij+2)，那么決策ij+1不需要被保留，刪去決策ij+1，再判斷決策ij+2是否不需要被保留。如此操作直到不需要?jiǎng)h除決策為止。第二十九頁(yè)，共四十一頁(yè)，編輯于2023年，星期二合理的序與維護(hù)方向

容易知道，平衡樹(shù)可以在O(logn)的時(shí)間內(nèi)求前驅(qū)、后繼，查找最大的不超過(guò)h(x)的元素。因?yàn)槊看尾迦胄碌臎Q策只需要進(jìn)行均攤O(1)次操作（可用類似于棧維護(hù)的方法證明），所以維護(hù)序列的總時(shí)間是O(nlogn)的。回答詢問(wèn)的總時(shí)間是O(qlogn)的。所以總時(shí)間復(fù)雜度就是O((n+q)logn)的。值得一提的是，只要對(duì)這個(gè)算法稍加改變，就可以在O(nlogn+輸出規(guī)模)的時(shí)間內(nèi)解決在線半平面交的問(wèn)題，因?yàn)槲覀冇?jì)算出的g恰好就是這些直線組成的最低折線上的轉(zhuǎn)折點(diǎn)。雖然這種方法可以高效處理從中間維護(hù)決策序列的情況，但畢竟平衡樹(shù)操作的常數(shù)因子不小，如果可以只在兩頭維護(hù)序列，就只需要用棧來(lái)維護(hù)，程序效率會(huì)大大提高。第三十頁(yè)，共四十一頁(yè)，編輯于2023年，星期二合理的序與維護(hù)方向

考慮離線半平面交問(wèn)題，給出n個(gè)二元一次方程Ax+By

C，求出可行域。我們只考慮這個(gè)問(wèn)題的關(guān)鍵步驟：給出一些直線y=kx+b，求出最低的一條折線（顯然這是上凸的）。由于最終的結(jié)果與處理直線的順序無(wú)關(guān)，我們先將這些直線按照k從大到小排序，然后應(yīng)用上面的方法。這時(shí)，這些“決策”的插入過(guò)程中，只需要從序列的尾部維護(hù)，這個(gè)操作用棧就可以高效的完成。最后剩下的“決策”就是按照從左到右順序的最低折線，而相鄰兩“決策”間的g，就是這些折線交點(diǎn)的橫坐標(biāo)。排序之后的這些操作，其時(shí)間復(fù)雜度總計(jì)O(n)。這個(gè)幾何問(wèn)題，我們甚至沒(méi)有畫(huà)一張圖，就用這種方法在O(nlogn)的時(shí)間內(nèi)高效的解決了。而算法效率的瓶頸是一開(kāi)始的排序，如果排序可以在O(n)時(shí)間內(nèi)完成，或者直線就是按斜率從大到小或斜率從小到大的順序給出，那么此方法的時(shí)間復(fù)雜度就是O(n)。這足以說(shuō)明此方法更應(yīng)該被作為一種思想來(lái)看待。第三十一頁(yè)，共四十一頁(yè)，編輯于2023年，星期二合理的序與維護(hù)方向

例4(USACOJAN07schul)要求維護(hù)一些不與y軸平行的直線。每次要么添加一條直線y=kx+b，要么詢問(wèn)當(dāng)x=p與這些直線的所有交點(diǎn)中的縱坐標(biāo)的最小的點(diǎn)。保證每條直線的斜率大于0，并且新加直線的橫截距-b/k比原來(lái)的直線的橫截距都大。并且保證每次詢問(wèn)的p總比最大橫截距大。由于直線并不是按照斜率遞增或遞減的順序添加的，使用上面的方法只能得到O((n+q)logn)的算法，而對(duì)于本題的數(shù)據(jù)，這個(gè)算法雖然比O(qn)的方法快了很多，但還是很慢。我們不妨再仔細(xì)分析一下題目特點(diǎn)，按順序?qū)⒚織l直線假如決策序列會(huì)怎樣呢？直線i比直線j(i<j)優(yōu)等價(jià)于當(dāng)kj>ki時(shí)，這等價(jià)于；當(dāng)kj≤ki時(shí)，這等價(jià)于，然而由于左邊不大于最大橫截距，而這個(gè)問(wèn)題又保證每次詢問(wèn)的x大于最大橫截距，所以這個(gè)條件等價(jià)于x

∞！第三十二頁(yè)，共四十一頁(yè)，編輯于2023年，星期二合理的序與維護(hù)方向

這樣，我們就得到了一個(gè)合適的函數(shù)g(i,j)，以及一個(gè)便于處理的序，這個(gè)序恰好就是直線插入的順序。所以這個(gè)問(wèn)題就被轉(zhuǎn)化為一個(gè)普通的棧維護(hù)問(wèn)題，由于這個(gè)序列的維護(hù)方法已經(jīng)在例2中給出，這里不再贅述。這樣，我們就在O(n+q)的時(shí)間解決了這個(gè)問(wèn)題。而解決這個(gè)問(wèn)題的關(guān)鍵是：有些結(jié)論雖然在全局并不成立，但在某個(gè)具有更多限制的局部?jī)?nèi)卻可以滿足。所以我們要充分利用題目特點(diǎn)，找到最適合的序，這個(gè)序有時(shí)就是以這個(gè)特殊的局部?jī)?nèi)的某些性質(zhì)為基礎(chǔ)的。第三十三頁(yè)，共四十一頁(yè)，編輯于2023年，星期二最優(yōu)決策的查找方式當(dāng)這個(gè)決策序列是使用棧在兩頭維護(hù)時(shí)：如果h(x)單調(diào)增或單調(diào)減，則可以利用這個(gè)單調(diào)性接著上次查找，在O(n+q)時(shí)間內(nèi)回答所有詢問(wèn)，如果這個(gè)h(x)的反復(fù)次數(shù)不多（例如凸等），也可以用接著上次查找的方法，其時(shí)間復(fù)雜度為O(|ans1-ans2|+|ans1-ans2|+···+|ansq-1-ansq|)。如果這個(gè)h(x)的變化很不規(guī)律，則可以用二分查找的方法在O(qlogn)時(shí)間內(nèi)回答所有詢問(wèn)。當(dāng)這個(gè)決策序列是從中間維護(hù)時(shí)，由于使用了平衡樹(shù)，我們也只能用平衡樹(shù)上的查找方法。相比之下，從中間維護(hù)決策序列無(wú)論是從決策的維護(hù)還是最優(yōu)決策的查找，都有很大劣勢(shì)，我們應(yīng)當(dāng)盡量避免（尋找適合的序）。第三十四頁(yè)，共四十一頁(yè)，編輯于2023年，星期二選擇合適的規(guī)劃方向例5(旅行)一條鐵路線上有N個(gè)城市，順序編號(hào)為1,2,…,N，TT希望從城市1到城市N。從城市i出發(fā)只能到達(dá)后面的某個(gè)點(diǎn)j，需要花費(fèi)(j-i)Ai的車(chē)票費(fèi)與Bj元的檢票費(fèi)。TT想知道從城市1出發(fā)到城市N所需要的最少花費(fèi)。假設(shè)d[i]為從城市1到城市i所需的最小費(fèi)用，則決策i不比決策j(i<j)等價(jià)于于是選擇Ai作為決策的序，就轉(zhuǎn)化為使用平衡樹(shù)從中間維護(hù)決策序列的問(wèn)題。根據(jù)上面的討論，這個(gè)算法的時(shí)間復(fù)雜度是O(nlogn)的。但由于使用平衡樹(shù)來(lái)維護(hù)，這個(gè)算法的常數(shù)因子不小。第三十五頁(yè)，共四十一頁(yè)，編輯于2023年，星期二選擇合適的規(guī)劃方向但是，如果定義d[i]為從車(chē)站i到車(chē)站N所花的最少代價(jià)，則此時(shí)，決策i不如決策j(i>j)等價(jià)于這時(shí)，我們可以按處理順序在決策序列末尾維護(hù)決策，這樣只需要用棧就可以維護(hù)決策序列。在查找最優(yōu)決策的時(shí)候，只需要使用二分查找的方法，就可以在O(nlogn)時(shí)間內(nèi)解決此問(wèn)題。雖然這個(gè)方法與上個(gè)方法具有一樣的理論時(shí)間復(fù)雜度，但由于棧維護(hù)和二分查找相對(duì)于平衡樹(shù)的常數(shù)因子非常小，在實(shí)踐中，這個(gè)方法相比上個(gè)方法存在