算法合集之淺談用極大化思想解決最大子矩形問題(參考版)
2025-01-12 19:42本頁面
【正文】 見 論文附件 .doc 說明：所有程序均在 Free Pascal IDE for Dos, Version 編譯運(yùn)行 參考書目 信息學(xué)奧林匹克 競賽指導(dǎo) 1997～ 1998競賽試題解析 吳文虎 王建德 著 IOI99 中國集訓(xùn)隊(duì)優(yōu)秀論文集 信息學(xué)奧林匹克（季刊） 《金牌之路 競賽輔導(dǎo)》 江文哉主編 陜西師范大學(xué)出版社出版 。 七、 附錄： 幾個(gè)例題的原題。 此外，如果采用極 大化思想，前面提到的兩種算法的復(fù)雜度已經(jīng)不能再降低了，因?yàn)闃O大有效子矩形的個(gè)數(shù)就是 O(NM)或 O(S2)的。雖然兩個(gè)算法看起來有著巨大的差別，但他們的本質(zhì)是相通的，都是利用極大化思想，從枚舉所有的極大有效子矩形入手，找出解決問題的方法。 在效率上，兩種算法對于不同的情況各有千秋。 五、小結(jié) 王知昆 第 10 頁 IOI2022 國家集訓(xùn)隊(duì)論文 設(shè)計(jì)算法要從問題的基本特征入手，找出解題的突破口。 算法 1： Test 1: Test 2: Test 3: Test 4: Test 5: Test 6: Test 7: Test 8: Test 9: Test 10: Test 11: Test 12: Test 13: Test 14: Test 15: 算法 2： Test 1: Test 2: Test 3: Test 4: Test 5: Test 6: Test 7: Test 8: Test 9: Test 10: Test 11: Test 12: Test 13: Test 14: Test 15: 以上，利用極大化思想和前面設(shè)計(jì)的兩個(gè)算法，通過轉(zhuǎn)換模型，解決了三個(gè)具有一定代表性的例題。 以下是第一種和第二種算法編程實(shí)現(xiàn)后在 USACO Training Program Gateway 上的運(yùn)行時(shí)間。因?yàn)?NT，所以從時(shí)間復(fù)雜度的角度看，第二種算法要比第一種算法好。下面分析兩種算法應(yīng)用在本題上的優(yōu)略。具體的 處理方法如下：對于每一個(gè)枚舉出的極大子矩形，如圖所示，如果它的邊長為 a、 b，那么它包含的極大子正方形的邊長即為 min(a,b)。這樣，問題的實(shí)質(zhì)和前面所說的最大子矩形問題是一樣的，同樣的，所采用的算法也是一樣的。且這個(gè)極大子正方形一定有兩條不相鄰的邊與這個(gè)包含它的極大子矩形的邊重合。根據(jù)這一點(diǎn)，可以得到一個(gè)重要的定理。如果是極大子矩形，那么不能再向外擴(kuò)展的充要條件是四條邊上都覆蓋了障礙點(diǎn)（【定理 2】 ）。 根據(jù)【定理 4】 ,我們只需要枚舉出所有的極大子正方形，就可以從中找出最大子正方形。這與前兩題的模型是否有相似之處呢？還是從最大子正方 形的本質(zhì)開始分析。 定義 有效子正方形 為內(nèi)部不包含任何障礙點(diǎn)的子正方形 定義 極大有效子正方形 為不能再向外擴(kuò)展的有效子正方形，一下簡稱極大子正方形 定義 最大有效子正方形 為所有有效子正方形中最大的一個(gè)（或多個(gè)），以下簡稱 最大子正方形 。 分析 ： 這題是矩形上的問題，但要求的是最大子正方形。 參數(shù)約定：牛場為 N N的，樹的棵數(shù)為 T。由于農(nóng)場上有一些樹，而且 Farmer John 又不想砍這些樹，因此要找出最大的一個(gè)不包含任何樹的一塊正方形場地。 可以看出，第一種算法并不適合這道題，因此最好還是采用第二種算法。 此外，由于矩形與矩陣的不同，所以在處理上會有一些小麻煩。同樣，兩種算法只需稍加修改就可以解決本題。再一次利用極大化思想，因?yàn)榫仃囍械臋?quán)值都是正的，所以最大權(quán)值子矩陣一定是一個(gè)極大子矩陣。以下簡稱為 最大權(quán)值子矩陣 。 有效子矩陣的權(quán)值 （只有有效子矩形才有權(quán)值）為這個(gè)子矩陣包含的所有點(diǎn)的權(quán)值 和。 定義： 有效子矩陣 為內(nèi)部不包含任
試題試卷相關(guān)推薦
鄂ICP備17016276號-1