算法合集之淺談補集轉(zhuǎn)化思想在統(tǒng)計問題中的應(yīng)用(編輯修改稿)
2024-11-12 20:33 本頁面
【文章內(nèi)容簡介】 此經(jīng)典的問題，用常規(guī)的方法能否解決呢？ 初步分析 實際上，用離散化可以設(shè)計出能夠接受的算法。 離散化的算法時間復(fù)雜度為 O(min{M,N}*L) 雖然對于原題勉強可以應(yīng)付，但是一旦數(shù)據(jù)規(guī)模再稍稍擴大一點，必定超時。 而且離散化的算法思考比較復(fù)雜，編程比較煩瑣。 幾個工具 在進一步地思考之前，我們先明確幾個小問題，以作為下面研究的工具 。 在一個 X行 Y列的矩形 A中放入一個 P行 Q列的矩形 B， 共有多少種擺放方案 ？ 結(jié)論一 ： 矩形 B能夠放入矩形 A中的充要條件是 X=P且 Y=Q， 所以如果 XP或 YQ， 方案數(shù)為 0。 否則矩形 B的左上角可以位于矩形 A的 1至 XP+1行 ， 1至YQ+1列 ， 也就是總共有 (XP+1)*(YQ+1)種擺放方案 。 矩形 A的左上角為 ( A X 1 , AY 1 ) ， 右下角為(AX2,AY2)， 矩形 B的左上角為 (BX1,BY1)， 右下角為 (BX2,BY2)， 如果存在某兩個格子 a∈ A，b∈ B且 a、 b相鄰或重合 ， 就稱 A和 B“ 相交 ” 。 如何判斷 A、 B是否相交 ？ 這個問題稍稍復(fù)雜一點 ， 但是仔細分析各種情況之后可以得出 結(jié)論二 ： A和 B相交的充要條件是 (AX1=BX2+1) and (AX2=BX11) and (AY1=BY2+1) and (AY2=AY11)。 幾個工具 X行 Y列 幾個工具 P行 Q列 2Q+Y列 2P+X行 設(shè)一個已經(jīng)擺放的矩形 A為 X行 Y列，新擺放的矩形 B為P行 Q列，矩形 B怎樣擺放才能和矩形 A相交呢？根據(jù)結(jié)論二我們直接就可以得出 結(jié)論三 ：矩形 B能夠與 A相交的所有擺放方案位于一個2P+X行， 2Q+Y列
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1