算法合集之多角度思考創(chuàng)造性思維(編輯修改稿)
2024-11-14 18:36 本頁面
【文章內(nèi)容簡(jiǎn)介】 2 jtos o nfjkihkih ????)_,( jtos o nf狀態(tài)的轉(zhuǎn)移 最后 )},_(2),_(1m i n {)_,(k l e f tn ums onhk l e f tn ums onhk l e f ttof r o mf?效率分析 由于狀態(tài)是 3維的，而轉(zhuǎn)移時(shí)需要枚舉 k、son、和 j，看上去時(shí)間復(fù)雜度巨大。 這是為什么 ? 剛才的分析通過狀態(tài)量和轉(zhuǎn)移量相乘來分析效率，每一維都不到 N。 j的總數(shù)是 n， son的總數(shù)也是 n，所以雖然要枚舉 3個(gè)，但是總的運(yùn)算量是一定的，時(shí)間復(fù)雜度為 。 )( 3 knO回顧 本題的動(dòng)態(tài)規(guī)劃是多維的，要通過分析建立狀態(tài) 在兄弟結(jié)點(diǎn)之間要通過類似背包問題的思想進(jìn)行第二次動(dòng)態(tài)規(guī)劃 不是單純的根據(jù)狀態(tài)量和轉(zhuǎn)移量分析時(shí)間復(fù)雜度，而是根據(jù)轉(zhuǎn)移總量分析 總量分析 均攤分析 例題解析 NOI03 逃學(xué)的小孩 IOI05 河流 NOI06 網(wǎng)絡(luò)收費(fèi) POI04 山洞 問題描述 M=2N個(gè)點(diǎn) ， 構(gòu)成一個(gè)滿二叉樹 配對(duì)收費(fèi)：對(duì)于每?jī)蓚€(gè)用戶 i, j (1≤ i j ≤ 2N ) 進(jìn)行收費(fèi) 。 用戶可以自行選擇兩種付費(fèi)方式 A、 B中的一種 ， 收取的費(fèi)用等于每?jī)晌徊煌脩襞鋵?duì)產(chǎn)生費(fèi)用之和 。 問題描述 I付費(fèi)方式 J付費(fèi)方式 nA與 nB大小關(guān)系 付費(fèi)系數(shù) k 實(shí)際付費(fèi) A A nAnB 2 k * Fi, j A B 1 B A 1 B B 0 A A nA≥ nB 0 A B 1 B A 1 B B 2 問題描述
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1