淺談?dòng)脴O大化思想解決最大子矩形問(wèn)題(編輯修改稿)
2025-04-22 02:28 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 個(gè)方向盡可能移動(dòng)所得到的有效子矩形稱為這個(gè)懸線所對(duì)應(yīng)的子矩形，那么所有懸線所對(duì)應(yīng)的有效子矩形的集合一定包含了所有極大子矩形的集合。定理3中的“盡可能”移動(dòng)指的是移動(dòng)到一個(gè)障礙點(diǎn)或者矩形邊界的位置。根據(jù)【定理3】可以發(fā)現(xiàn)，通過(guò)枚舉所有的懸線，就可以枚舉出所有的極大子矩形。由于每個(gè)懸線都與它底部的那個(gè)點(diǎn)一一對(duì)應(yīng)，所以懸線的個(gè)數(shù)＝(n1)m（以矩形中除了頂部的點(diǎn)以外的每個(gè)點(diǎn)為底部，都可以得到一個(gè)懸線，且沒有遺漏）。如果能做到對(duì)每個(gè)懸線的操作時(shí)間都為O(1)，那么整個(gè)算法的復(fù)雜度就是O(NM)。這樣，我們看到了解決問(wèn)題的希望?，F(xiàn)在的問(wèn)題是，怎樣在O(1)的時(shí)間內(nèi)完成對(duì)每個(gè)懸線的操作。我們知道，每個(gè)極大子矩形都可以通過(guò)一個(gè)懸線左右平移得到。所以，對(duì)于每個(gè)確定了底部的懸線，我們需要知道有關(guān)于它的三個(gè)量：頂部、左右最多能移動(dòng)到的位置。對(duì)于底部為(i,j)的懸線，設(shè)它的高為hight[i,j],左右最多能移動(dòng)到的位置為left[i,j],right[i,j]。為了充分利用以前得到的信息，我們將這三個(gè)函數(shù)用遞推的形式給出。對(duì)于以點(diǎn)(i,j)為底部的懸線：如果點(diǎn)(i－1,j)為障礙點(diǎn)，那么，顯然以(i,j)為底的懸線高度為1，而且左右均可以移動(dòng)到整個(gè)矩形的左右邊界，即237。left[i,j]=0即left[i,j]=max237。236。left[i1,j]王知昆 第6頁(yè) IOI2003國(guó)家集訓(xùn)隊(duì)論文236。height[i,j]=1239。238。239。right[i,j]=m如果點(diǎn)(i－1,j)不是障礙點(diǎn)，那么，以(i,j)為底的懸線就等于以(i1,j)為底的懸線＋點(diǎn)(i,j)到點(diǎn)(i1,j)的線段。因此，height[i,j]=height[i1,j]+1。比較麻煩的是左右邊界，先考慮left[i,j]。如下圖所示，(i,j)對(duì)應(yīng)的懸線左右能移動(dòng)的位置要在(i1,j)的基礎(chǔ)上變化。238。(i1,j)左邊第一個(gè)障礙點(diǎn)的位置left[i1,j]某個(gè)障礙(i1,j)(i,j):當(dāng)前l(fā)eft[i,j]點(diǎn)239。height[i,j]=height[i1,j]+1237。left[i,j]=max237。236。left[i1,j]239。239。right[i,j]=min237。236。right[i1,j]right[i,j]的求法類似。綜合起來(lái)，可以得到這三個(gè)參數(shù)的遞推式：236。239。239。239。 238。(i1,j)左邊第一個(gè)障礙點(diǎn)位置（邊界0也算障礙點(diǎn)）239。238。239。 238。(i1,j)右邊第一個(gè)障礙點(diǎn)位置（邊界m也算障礙點(diǎn)）這樣做充分利用了以前得到的信息，使每個(gè)懸線的處理時(shí)間復(fù)雜度為O(1)。對(duì)于以點(diǎn)(i,j)為底的懸線對(duì)應(yīng)的子矩形，它的面積為(right[i,j]left[i,j])*height[i,j]。這樣最后問(wèn)題的解就是：Result＝max{(right[i,j]left[i,j])*height[i,j](1=in,1=j=m)整個(gè)算法的時(shí)間復(fù)雜度為O(NM)，空間復(fù)雜度是O(NM)。王知昆 第7頁(yè) IOI2003國(guó)家集訓(xùn)隊(duì)論文兩個(gè)算法的對(duì)比：以上說(shuō)了兩種具有一定通用性的處理算法，時(shí)間復(fù)雜度分別為O(S2)和O(NM)。兩種算法分別適用于不同的情況。從時(shí)間復(fù)雜度上來(lái)看，第一種算法對(duì)于障礙點(diǎn)稀疏的情況比較有效，第二種算法則與障礙點(diǎn)個(gè)數(shù)的多少?zèng)]有直接的關(guān)系（當(dāng)然，障礙點(diǎn)較少時(shí)可以通過(guò)對(duì)障礙點(diǎn)坐標(biāo)的離散化來(lái)減小處理矩形的面積，不過(guò)這樣比較麻煩，不如第一種算法好），適用于障礙點(diǎn)密集的情況。五、例題將前面提出的兩種算法運(yùn)用于具體的問(wèn)題。 WinterCamp2002,奶牛浴場(chǎng)分析：題目的數(shù)學(xué)模型就是給出一個(gè)矩形和矩形
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1