淺析信息學(xué)中分與合.ppt

淺析信息學(xué)中的“分”與“合”,福建省福州第三中學(xué) 楊沐,引言,分 “分”的思想是將一個(gè)難以直接解決的大問題，轉(zhuǎn)化成一些規(guī)模較小或限制某些條件的子問題來思考，以求將問題解決。,合 “合”的思想與“分”相對(duì)，是將一些零散的小問題的解決合并成一個(gè)大問題，從而取得整個(gè)問題的解決。,話說天下大勢(shì)，合久必分，分久必合,引言,例一牛奶模版 例二樹的重建 例三最優(yōu)序列,二分 化歸,運(yùn)用“分”與“合”思想方法解題的精髓在于通過在“分”與“合”之間的轉(zhuǎn)化，找出解決問題的關(guān)鍵，從而解決問題。 “分治法”是運(yùn)用“分”與“合”思想方法解題的重要應(yīng)用，此外，“分”與“合”的思想方法還有更多、更廣泛的應(yīng)用。,N,K限制下最優(yōu)化問題N,K,Len限制下存在性問題,規(guī)模為n的問題規(guī)模為n-1的問題,例三最優(yōu)序列,給定一個(gè)長度為N的正整數(shù)序列。 求一個(gè)子序列，使得原序列中任意長度為M的子串中被選出的元素不超過K個(gè)。 要求選出的元素之和最大。 數(shù)據(jù)范圍： 1N1000 1K，M100,例三最優(yōu)序列,輸入數(shù)據(jù)： N=10，M=4，K=2 7，3，4，8，2，6，5，7，4，8 輸出答案： 36 7，3，4，8，2，6，5，7，4，8,例三最優(yōu)序列分析,動(dòng)態(tài)規(guī)劃 線段樹？ 怎么辦？,“分”,超時(shí),無從入手,O(2MN)！,O(21001000),例三最優(yōu)序列“分”繁為簡(jiǎn),動(dòng)態(tài)規(guī)劃之所以不可行，原因在于題目中K和M的范圍太大了！ 利用“分”的思想，我們嘗試限制K，令K=1，也就是對(duì)于長度為M的子串，最多只選一個(gè)元素作為原題的一個(gè)子問題：,例三最優(yōu)序列子問題,給定一個(gè)長度為N的正整數(shù)序列。 求一個(gè)子序列，使得原序列中任意長度為M的子串中被選出的元素不超過1個(gè)。 要求選出的元素之和最大。 數(shù)據(jù)范圍： 1N1000 1M100,例三最優(yōu)序列“分”繁為簡(jiǎn),對(duì)于這個(gè)子問題，由于K做了限制，我們可以用動(dòng)態(tài)規(guī)劃來解決這個(gè)問題。 設(shè)dpi表示前i個(gè)元素，在滿足題意的前提下選出的最大和 dpi=max(dpi-1,dpi-M+valuei) iM dpi=max(dpi-1,valuei) 0iM dp0=0,例三最優(yōu)序列進(jìn)一步分析,子問題,原問題,1,K,例三最優(yōu)序列進(jìn)一步分析,命題 原問題的解集等價(jià)于由K組互不相交的子問題的解組成的解集。 引理一 原問題的任意一組解都可以由K組不相交的子問題的解組成。 引理二 任意K組不相交的子問題的解的并均為原問題的解。,引理一 原問題的任意一組解都可以由K組不相交的子問題的解組成。 證明 對(duì)于原問題的任意一解P=a1,a2,a3at，a1a2a3at。設(shè)sumi表示該解在區(qū)間1,i內(nèi)取出的元素個(gè)數(shù)，則根據(jù)題意滿足不等式： sumi-sumi-MK,以下，我們給出一種構(gòu)造法使之能產(chǎn)生一組與該解等價(jià)的K個(gè)子問題的解。 設(shè)K個(gè)子問題的解分別為P0,P1,P2Pk-1， 令Pi=aj | ji (mod K) sumi-sumi-MK ai-ai-kM P0,P1,P2Pk-1均為合法的子問題的解 又因?yàn)镻0P1P2Pk-1=P，因此我們成功地構(gòu)造出了子問題的解。,引理二 任意K組不相交的子問題的解的并均為原問題的解。 證明 設(shè)K個(gè)子問題的不相交的解分別為P0,P1,P2Pk-1 ， Pi=ai1,ai2,ai3ail，ai1ai2ai3ail 對(duì)于任意長度為M的區(qū)間，Pi至多只有一個(gè)元素在其內(nèi)部,設(shè)P=P0P1P2Pk-1， 則對(duì)于任意長度為M的區(qū)間，P在其內(nèi)部選出的元素個(gè)數(shù)不超過K個(gè) 任意K組互不相交的子問題的解的并都是原問題的合法解。 引理一與引理二分別證明了命題的充分性和必要性，因此該命題成立,例三最優(yōu)序列進(jìn)一步分析,題目中存在著一個(gè)潛條件，即： 每個(gè)元素只能被選一次 若直接套用K次動(dòng)態(tài)規(guī)劃來求解，有可能導(dǎo)致某個(gè)元素被取多次，無法滿足題目中的這個(gè)條件。,例三最優(yōu)序列進(jìn)一步分析,N=10，M=4，K=2 3 3 3 3 動(dòng)態(tài)規(guī)劃：12 貪心：9,標(biāo)準(zhǔn)答案：10,1,1,1,1,1,1,1,1,3,3,并 1 3 1 3 1,并 1 3 1 1 3 1,考慮動(dòng)態(tài)規(guī)劃與貪心之所以不能得到正確解，其關(guān)鍵原因在于題目中存在著一個(gè)元素只能被取一次的限制，而對(duì)于這種限制各點(diǎn)被選取次數(shù)的題目，我們通常使用網(wǎng)絡(luò)流來解決，那么這道題是否也能通過轉(zhuǎn)化圖論模型來使用網(wǎng)絡(luò)流解決呢？答案是肯定的。,例三最優(yōu)序列整體分析,例三最優(yōu)序列整體分析,構(gòu)造帶權(quán)網(wǎng)絡(luò)G=(V,A,C) 序列中的每個(gè)元素i用頂點(diǎn)i與i表示，ii連邊，容量為1，費(fèi)用為該元素的數(shù)值valuei，圖中包含源S與匯T。 所有點(diǎn)i向點(diǎn)(i+1)連邊，容量為+ ，費(fèi)用為0 源S向所有點(diǎn)i各連一條邊，容量為+，費(fèi)用為0 所有點(diǎn)i向匯T各連一條邊，容量為+，費(fèi)用為0 所有點(diǎn)i向點(diǎn)(i+M)連邊，容量為+ ，費(fèi)用為0,3,2,1,n,1,2,3,n,T,S,容量 = 1 費(fèi)用 = valuei,容量 = + 費(fèi)用 = 0,例三最優(yōu)序列整體分析,構(gòu)圖完成之后，網(wǎng)絡(luò)中的每個(gè)單位流量表示一個(gè)子問題的解，因此，我們只需要在網(wǎng)絡(luò)中尋找K次最大費(fèi)用增廣路即可得到答案。 由于這張圖的邊數(shù)與頂點(diǎn)數(shù)同階，若使用SPFA算法求增廣軌，則期望時(shí)間復(fù)雜度僅為O(KN)，是個(gè)十分優(yōu)秀的算法。,總結(jié),分,合,對(duì)立,統(tǒng)一,辨證關(guān)系,分中有合，合中有分,轉(zhuǎn)化,“分”的思想幫助我們迅速地切入問題核心，但若過分細(xì)化則會(huì)使問題太過凌亂，失去求解的方向；而“合”的思想則以線串珠，使各種紛雜無序的問題具有了整體性。,善于歸納總結(jié),勇于創(chuàng)新,謝 謝,總結(jié)：“分”與“合”雖然對(duì)立，卻沒有明顯的分界。一道問題若使用“分”的方法，則必然有“合”的操作，正所謂“分中有合，合中有分”，這兩者相互對(duì)立，各有優(yōu)勢(shì)，卻又相互補(bǔ)充，“分”的思想幫助我們迅速地切入問題核心，但若過分細(xì)化則會(huì)使問題太過凌亂，失去求解的方向；而“合”的思想則以線串珠，使各種紛雜無序的問題具有了整體性，這正體現(xiàn)了兩者之間的辨證關(guān)系。 運(yùn)用“分”與“合”的思想，對(duì)于不同的題目需要不同的分析，其精髓就在于“轉(zhuǎn)化”。無論是“分”還是“合”都是朝著將問題轉(zhuǎn)化為更加便于思考的方向前進(jìn)，而在這路途中，又需要我們善于歸納總結(jié)。只有將已有的知識(shí)與“分合”思想有機(jī)地結(jié)合起來，同時(shí)勇于創(chuàng)新，不斷積累經(jīng)驗(yàn)，我們才能從千變?nèi)f化的題目中找尋出本質(zhì)，從而更快更有效地解決實(shí)際問題。,整體,部分,網(wǎng)絡(luò)流！,轉(zhuǎn)化目標(biāo),動(dòng)態(tài)規(guī)劃,貪心,小結(jié),線段樹無法解決該題的原因,因?yàn)樵瓎栴}是要求對(duì)于任意長度為M的區(qū)間，都限制了取數(shù)不超過K個(gè)。而這些區(qū)間有互相有交，這使得線段樹很難準(zhǔn)確的表示一個(gè)狀態(tài)并進(jìn)行處理。 更重要的是，線段樹只是一個(gè)用來提升算法效率的輔助工具，