算法合集之《多角度思考創(chuàng)造性思維》

1、算法合集之多角度思考創(chuàng)造性思維算法合集之多角度思考創(chuàng)造性思維引入引入信息學(xué)競賽中通常會(huì)出現(xiàn)這樣的問題：給一棵樹，要求以最少的代價(jià)（或取得最大收益）完成給定的操作有很多問題都是在樹和最優(yōu)性的基礎(chǔ)上進(jìn)行了擴(kuò)充和加強(qiáng)，從而變成了棘手的問題這類問題通常規(guī)模較大，枚舉算法的效率無法勝任，貪心算法不能得到最優(yōu)解，因此要用動(dòng)態(tài)規(guī)劃解決算法合集之多角度思考創(chuàng)造性思維引入引入在近幾年信息學(xué)競賽中，需要運(yùn)用樹型動(dòng)態(tài)規(guī)劃解決的問題頻繁出現(xiàn)這些問題變化繁多，各類思想精華滲透其中，對(duì)選手分析問題的能力和解題創(chuàng)造性思維有著較高的要求，因此它在競賽中占據(jù)了重要地位算法合集之多角度思考創(chuàng)造性思維引入引入在此，我將分析近幾年國

2、際比賽、全國比賽中的樹型動(dòng)態(tài)規(guī)劃問題，重點(diǎn)探討幾種樹型動(dòng)態(tài)規(guī)劃問題的解法，并從這些問題的分析過程中，提煉出解決這類問題的思想方法多角度思考，創(chuàng)造性思維。旨在論述解決問題的思維過程，而不僅僅是解題方法算法合集之多角度思考創(chuàng)造性思維例題解析例題解析NOI03 逃學(xué)的小孩 IOI05 河流 NOI06 網(wǎng)絡(luò)收費(fèi) POI04 山洞 算法合集之多角度思考創(chuàng)造性思維問題描述問題描述n個(gè)伐木的村莊在0號(hào)結(jié)點(diǎn)有一個(gè)巨大的伐木場，木料被砍下后，順著河流而被運(yùn)到0號(hào)結(jié)點(diǎn)的伐木場為了減少運(yùn)輸木料的費(fèi)用，再額外建造k個(gè)伐木場這些伐木場建造后，木料可以在運(yùn)輸過程中第一個(gè)碰到的新伐木場被處理。算法合集之多角度思考創(chuàng)造性思

3、維問題描述問題描述所有的河流都不會(huì)分叉，也就是說，每一個(gè)村子，順流而下都只有一條路到0號(hào)結(jié)點(diǎn)。已知每個(gè)村子每年要產(chǎn)多少木料，求在哪些村子建設(shè)伐木場能獲得最小的運(yùn)費(fèi)。 N100K50算法合集之多角度思考創(chuàng)造性思維問題抽象問題抽象本題的題意很明確，即建立k個(gè)伐木廠，使得把所有木材運(yùn)送到最近的祖先伐木廠的費(fèi)用最小。由于題目給定的是一棵樹，數(shù)據(jù)規(guī)模又比較大，很容易聯(lián)想到樹型動(dòng)態(tài)規(guī)劃。算法合集之多角度思考創(chuàng)造性思維狀態(tài)的確立狀態(tài)的確立首先必須有的是當(dāng)前點(diǎn)及以當(dāng)前點(diǎn)為根的子樹中，一共建立了多少伐木廠，但是這顯然是不夠的，因?yàn)檫@個(gè)狀態(tài)中沒有任何與伐木廠位置相關(guān)的信息。因此我們還需要再加一維。加上有關(guān)伐木廠的

4、位置的信息。 )_,(klefttofromf表示把以from為根的子樹中建立kleft個(gè)伐木廠，把木材全部運(yùn)送到最近的祖先伐木廠，所需要的費(fèi)用，并且from有一個(gè)祖先伐木廠為to_。 （注意到這里to_僅僅是from的祖先伐木廠，而未必是from的最近祖先伐木廠，這是為什么呢？）算法合集之多角度思考創(chuàng)造性思維狀態(tài)的轉(zhuǎn)移狀態(tài)的轉(zhuǎn)移狀態(tài)轉(zhuǎn)移分2種情況討論： 在from建立伐木廠 不在from建立伐木廠算法合集之多角度思考創(chuàng)造性思維狀態(tài)的轉(zhuǎn)移狀態(tài)的轉(zhuǎn)移在from建立伐木廠：即分配kleft個(gè)伐木廠給from的子結(jié)點(diǎn)，使得費(fèi)用最小。這分配的過程，也就相當(dāng)于背包問題。 h1是用來解背包問題的臨時(shí)數(shù)組，

5、son是from的兒子結(jié)點(diǎn)。),(), 1( 1),( 1jfromsonfjkihkih算法合集之多角度思考創(chuàng)造性思維狀態(tài)的轉(zhuǎn)移狀態(tài)的轉(zhuǎn)移不在from建立伐木廠：依然是分配kleft個(gè)伐木廠給from的子結(jié)點(diǎn)，使得費(fèi)用最小。不過不同的是，權(quán)不是 而是 ，因?yàn)閒rom處不一定有伐木廠。 h2是用來解背包問題的臨時(shí)數(shù)組，son是from的兒子結(jié)點(diǎn)。),(jfromsonf)_,(), 1(2),(2jtosonfjkihkih)_,(jtosonf算法合集之多角度思考創(chuàng)造性思維狀態(tài)的轉(zhuǎn)移狀態(tài)的轉(zhuǎn)移最后),_(2),_( 1min)_,(kleftnumsonhkleftnumsonhkleftt

6、ofromf算法合集之多角度思考創(chuàng)造性思維效率分析效率分析由于狀態(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ù)雜度為 。)(3knO算法合集之多角度思考創(chuàng)造性思維回顧回顧本題的動(dòng)態(tài)規(guī)劃是多維的，要通過分析本題的動(dòng)態(tài)規(guī)劃是多維的，要通過分析建立狀態(tài)建立狀態(tài)在兄弟結(jié)點(diǎn)之間要通過類似背包問題的在兄弟結(jié)點(diǎn)之間要通過類似背包問題的思想進(jìn)行第二次動(dòng)態(tài)規(guī)劃思想進(jìn)行第二次動(dòng)態(tài)規(guī)劃不是單純的根據(jù)狀態(tài)量和轉(zhuǎn)移量分析時(shí)不是單純的根據(jù)狀態(tài)量和

7、轉(zhuǎn)移量分析時(shí)間復(fù)雜度，而是根據(jù)轉(zhuǎn)移總量分析間復(fù)雜度，而是根據(jù)轉(zhuǎn)移總量分析總量分析均攤分析算法合集之多角度思考創(chuàng)造性思維例題解析例題解析NOI03 逃學(xué)的小孩 IOI05 河流 NOI06 網(wǎng)絡(luò)收費(fèi) POI04 山洞 算法合集之多角度思考創(chuàng)造性思維問題描述問題描述M=2N個(gè)點(diǎn)，構(gòu)成一個(gè)滿二叉樹配對(duì)收費(fèi)：對(duì)于每兩個(gè)用戶i, j (1i j 2N ) 進(jìn)行收費(fèi)。用戶可以自行選擇兩種付費(fèi)方式A、B中的一種，收取的費(fèi)用等于每兩位不同用戶配對(duì)產(chǎn)生費(fèi)用之和。算法合集之多角度思考創(chuàng)造性思維問題描述問題描述I付費(fèi)方式J付費(fèi)方式nA與nB大小關(guān)系付費(fèi)系數(shù)k實(shí)際付費(fèi)AAnAnB2k * Fi, jAB1BA1BB0

8、AAnAnB0AB1BA1BB2算法合集之多角度思考創(chuàng)造性思維問題描述問題描述對(duì)于用戶i，如果他/她想改變付費(fèi)方式（由A改為B或由B改為A），就必須支付Ci元給網(wǎng)絡(luò)公司以修改檔案。給定每個(gè)用戶注冊時(shí)所選擇的付費(fèi)方式以及Ci，試求這些用戶應(yīng)該如何選擇自己的付費(fèi)方式以使得總費(fèi)用最少（更改付費(fèi)方式費(fèi)用+配對(duì)收費(fèi)的費(fèi)用）。 N10 算法合集之多角度思考創(chuàng)造性思維問題轉(zhuǎn)化問題轉(zhuǎn)化配對(duì)收費(fèi)的規(guī)則nB較多時(shí)， AA 收費(fèi)系數(shù)為2n AB 收費(fèi)系數(shù)為1n BB 收費(fèi)系數(shù)為0n其他情況反之設(shè)想：nB較多時(shí)，在每一個(gè)A結(jié)點(diǎn)上有1個(gè)收費(fèi)系數(shù)n否則在每一個(gè)B結(jié)點(diǎn)上有1個(gè)收費(fèi)系數(shù)單點(diǎn)收費(fèi)算法合集之多角度思考創(chuàng)造性思維狀

9、態(tài)的確立狀態(tài)的確立狀態(tài)的設(shè)計(jì)應(yīng)該與以i點(diǎn)為根的子樹中A的個(gè)數(shù)有關(guān)，但僅僅這樣是不夠的，因?yàn)檫@些點(diǎn)是按A收費(fèi)還是B收費(fèi)還與以它每個(gè)祖先為根的子樹中，A多還是B多有關(guān)。因此，這也是需要記錄的。),(kjif點(diǎn)i所管轄的所有用戶中，有j個(gè)用戶為A，在i的每個(gè)祖先u上，如果nanb，則標(biāo)0，否則標(biāo)1，這個(gè)數(shù)列可以用二進(jìn)制表示，用k記錄，在這種情況下的最少花費(fèi)。算法合集之多角度思考創(chuàng)造性思維狀態(tài)的轉(zhuǎn)移狀態(tài)的轉(zhuǎn)移狀態(tài)轉(zhuǎn)移方程，其實(shí)就是將j個(gè)用戶分配給i的左右子節(jié)點(diǎn)，并更改k 2),(, 1),(min),(wskujrightfwskuleftfkjif算法合集之多角度思考創(chuàng)造性思維狀態(tài)的轉(zhuǎn)移狀態(tài)的轉(zhuǎn)移當(dāng)

10、i是葉節(jié)點(diǎn)時(shí)，可以根據(jù)k算出i與其它用戶配對(duì)收費(fèi)時(shí)所要交的費(fèi)用，再根據(jù)i的初始情況加上AB的轉(zhuǎn)化費(fèi)用。 算法合集之多角度思考創(chuàng)造性思維效率分析效率分析粗略看來，空間復(fù)雜度是 ，時(shí)間復(fù)雜度是 ，對(duì)于本題的數(shù)據(jù)可以同時(shí)超空間和超時(shí)間了。不過這只是很粗略的分析，這些狀態(tài)中有很多是取不到的。 )(3mO)(4mO算法合集之多角度思考創(chuàng)造性思維效率分析效率分析把根節(jié)點(diǎn)看做第0層，葉節(jié)點(diǎn)就是第n層，對(duì)于任意的第i層，A用戶的個(gè)數(shù)最多只有 ，而祖先結(jié)點(diǎn)只有i個(gè)，即k最大只有 ，把 的后兩維合并成一維，空間復(fù)雜度其實(shí)只有 。 in2i2),(kjif)(2mO算法合集之多角度思考創(chuàng)造性思維效率分析效率分析再看

11、時(shí)間復(fù)雜度，對(duì)于第i層，有 個(gè)結(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的狀態(tài)數(shù)是O(m)的，狀態(tài)轉(zhuǎn)移的復(fù)雜度是 ，所以每層的復(fù)雜度是 ?？偣灿衝層，所以狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度是 。i2)2(inO)(2mO)(2nmO算法合集之多角度思考創(chuàng)造性思維回顧回顧對(duì)收費(fèi)規(guī)則進(jìn)行轉(zhuǎn)化對(duì)收費(fèi)規(guī)則進(jìn)行轉(zhuǎn)化對(duì)時(shí)間復(fù)雜度進(jìn)行均攤分析對(duì)時(shí)間復(fù)雜度進(jìn)行均攤分析第二點(diǎn)在樹型動(dòng)態(tài)規(guī)劃中有著廣泛的運(yùn)第二點(diǎn)在樹型動(dòng)態(tài)規(guī)劃中有著廣泛的運(yùn)用，本題通過粗略的分析會(huì)超時(shí)，但是用，本題通過粗略的分析會(huì)超時(shí)，但是仔細(xì)分析之后，發(fā)現(xiàn)時(shí)間復(fù)雜度比粗略仔細(xì)分析之后，發(fā)現(xiàn)時(shí)間復(fù)雜度比粗略的分析少了一維的分析少了一維算法合集之多角度思考創(chuàng)造性思維總結(jié)總結(jié) 這這2個(gè)例題從不同方面闡述了樹型動(dòng)態(tài)規(guī)個(gè)例題從不同方面闡述了樹型動(dòng)態(tài)規(guī)劃的解題方法，如：劃的解題方法，如：n多維動(dòng)態(tài)規(guī)劃多維動(dòng)態(tài)規(guī)劃n兄弟結(jié)點(diǎn)之間通過類似背包的思想進(jìn)兄弟結(jié)點(diǎn)之間通過類似背包的思想進(jìn)行第二次動(dòng)態(tài)規(guī)劃行第二次動(dòng)態(tài)規(guī)劃n對(duì)復(fù)雜度的均攤分析對(duì)復(fù)雜度的均攤分析這些方法在比賽中有著廣泛的運(yùn)用這些方法在比賽中有著廣泛的運(yùn)用算法合集之多角度思考創(chuàng)造性思維總結(jié)總結(jié)在此過程中，我認(rèn)識(shí)到：面對(duì)陌生的問題，在此過程中，我認(rèn)識(shí)到：面對(duì)陌生的問題，一方面要深入分析問題的屬性，挖掘問題一方面