算法合集之《淺析信息學(xué)中的“分”與“合”》-預(yù)覽頁(yè)
【正文】 化歸 ?運(yùn)用“分”與“合”思想方法解題的精髓在于通過在“分”與“合”之間的轉(zhuǎn)化，找出解決問題的關(guān)鍵，從而解決問題。 ?合 ?“合”的思想與“分”相對(duì)，是將一些零散的小問題的解決合并成一個(gè)大問題，從而取得整個(gè)問題的解決。 ?求一個(gè)子序列，使得原序列中任意長(zhǎng)度為 M的子串中被選出的元素不超過 K個(gè)。 ?要求選出的元素之和最大。 ? 引理二 任意 K組不相交的子問題的解的并均為原問題的解。 ?所有點(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)用 = value[i] +∞ 0 [例三 ]最優(yōu)序列 —— 整體分析 ?構(gòu)圖完成之后，網(wǎng)絡(luò)中的每個(gè)單位流量表示一個(gè)子問題的解，因此，我們只需要在網(wǎng)絡(luò)中尋找 K次最大費(fèi)用增廣路即可得到答案
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1