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