8陳瑜希多角度思考 創(chuàng)造性思維

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

2、型動態(tài)規(guī)劃問題，重點探討幾種樹型動態(tài)規(guī)劃問題的解法，并從這些問題的分析過程中，提煉出解決這類問題的思想方法多角度思考，創(chuàng)造性思維。 旨在論述解決問題的思維過程，而不僅僅是解題方法,例題解析,NOI03 逃學(xué)的小孩 IOI05 河流 NOI06 網(wǎng)絡(luò)收費 POI04 山洞,問題描述,n個伐木的村莊 在0號結(jié)點有一個巨大的伐木場，木料被砍下后，順著河流而被運到0號結(jié)點的伐木場 為了減少運輸木料的費用，再額外建造k個伐木場 這些伐木場建造后，木料可以在運輸過程中第一個碰到的新伐木場被處理。,問題描述,所有的河流都不會分叉，也就是說，每一個村子，順流而下都只有一條路到0號結(jié)點。 已知每個村子每年要產(chǎn)多

3、少木料，求在哪些村子建設(shè)伐木場能獲得最小的運費。 N100 K50,問題抽象,本題的題意很明確，即建立k個伐木廠，使得把所有木材運送到最近的祖先伐木廠的費用最小。 由于題目給定的是一棵樹，數(shù)據(jù)規(guī)模又比較大，很容易聯(lián)想到樹型動態(tài)規(guī)劃。,狀態(tài)的確立,首先必須有的是當(dāng)前點及以當(dāng)前點為根的子樹中，一共建立了多少伐木廠，但是這顯然是不夠的，因為這個狀態(tài)中沒有任何與伐木廠位置相關(guān)的信息。因此我們還需要再加一維。加上有關(guān)伐木廠的位置的信息。,表示把以from為根的子樹中建立kleft個伐木廠，把木材全部運送到最近的祖先伐木廠，所需要的費用，并且from有一個祖先伐木廠為to_。 （注意到這里to_僅僅是fr

4、om的祖先伐木廠，而未必是from的最近祖先伐木廠，這是為什么呢？）,狀態(tài)的轉(zhuǎn)移,狀態(tài)轉(zhuǎn)移分2種情況討論： 在from建立伐木廠 不在from建立伐木廠,狀態(tài)的轉(zhuǎn)移,在from建立伐木廠： 即分配kleft個伐木廠給from的子結(jié)點，使得費用最小。這分配的過程，也就相當(dāng)于背包問題。 h1是用來解背包問題的臨時數(shù)組，son是from的兒子結(jié)點。,狀態(tài)的轉(zhuǎn)移,不在from建立伐木廠： 依然是分配kleft個伐木廠給from的子結(jié)點，使得費用最小。 不過不同的是，權(quán)不是 而是 ，因為from處不一定有伐木廠。 h2是用來解背包問題的臨時數(shù)組，son是from的兒子結(jié)點。,狀態(tài)的轉(zhuǎn)移,最后,效率分析,

5、由于狀態(tài)是3維的，而轉(zhuǎn)移時需要枚舉k、son、和j，看上去時間復(fù)雜度巨大。 這是為什么? 剛才的分析通過狀態(tài)量和轉(zhuǎn)移量相乘來分析效率，每一維都不到N。 j的總數(shù)是n，son的總數(shù)也是n，所以雖然要枚舉3個，但是總的運算量是一定的，時間復(fù)雜度為 。,回顧,本題的動態(tài)規(guī)劃是多維的，要通過分析建立狀態(tài) 在兄弟結(jié)點之間要通過類似背包問題的思想進(jìn)行第二次動態(tài)規(guī)劃 不是單純的根據(jù)狀態(tài)量和轉(zhuǎn)移量分析時間復(fù)雜度，而是根據(jù)轉(zhuǎn)移總量分析,總量分析 均攤分析,例題解析,NOI03 逃學(xué)的小孩 IOI05 河流 NOI06 網(wǎng)絡(luò)收費 POI04 山洞,問題描述,M=2N個點，構(gòu)成一個滿二叉樹 配對收費：對于每兩個用戶

6、i, j (1i j 2N ) 進(jìn)行收費。 用戶可以自行選擇兩種付費方式A、B中的一種，收取的費用等于每兩位不同用戶配對產(chǎn)生費用之和。,問題描述,問題描述,對于用戶i，如果他/她想改變付費方式（由A改為B或由B改為A），就必須支付Ci元給網(wǎng)絡(luò)公司以修改檔案。 給定每個用戶注冊時所選擇的付費方式以及Ci，試求這些用戶應(yīng)該如何選擇自己的付費方式以使得總費用最少（更改付費方式費用+配對收費的費用）。 N10,問題轉(zhuǎn)化,配對收費的規(guī)則 B較多時， AA 收費系數(shù)為2 AB 收費系數(shù)為1 BB 收費系數(shù)為0 其他情況反之 設(shè)想： B較多時，在每一個A結(jié)點上有1個收費系數(shù) 否則在每一個B結(jié)點上有1個收費系

7、數(shù),單點收費,狀態(tài)的確立,狀態(tài)的設(shè)計應(yīng)該與以i點為根的子樹中A的個數(shù)有關(guān)，但僅僅這樣是不夠的，因為這些點是按A收費還是B收費還與以它每個祖先為根的子樹中，A多還是B多有關(guān)。因此，這也是需要記錄的。,點i所管轄的所有用戶中，有j個用戶為A，在i的每個祖先u上，如果nanb，則標(biāo)0，否則標(biāo)1，這個數(shù)列可以用二進(jìn)制表示，用k記錄，在這種情況下的最少花費。,狀態(tài)的轉(zhuǎn)移,狀態(tài)轉(zhuǎn)移方程，其實就是將j個用戶分配給i的左右子節(jié)點，并更改k,狀態(tài)的轉(zhuǎn)移,當(dāng)i是葉節(jié)點時，可以根據(jù)k算出i與其它用戶配對收費時所要交的費用，再根據(jù)i的初始情況加上AB的轉(zhuǎn)化費用。,效率分析,粗略看來，空間復(fù)雜度是 ，時間復(fù)雜度是 ，對

8、于本題的數(shù)據(jù)可以同時超空間和超時間了。 不過這只是很粗略的分析，這些狀態(tài)中有很多是取不到的。,效率分析,把根節(jié)點看做第0層，葉節(jié)點就是第n層，對于任意的第i層，A用戶的個數(shù)最多只有 ，而祖先結(jié)點只有i個，即k最大只有 ，把 的后兩維合并成一維，空間復(fù)雜度其實只有 。,效率分析,再看時間復(fù)雜度，對于第i層，有 個結(jié)點，每個節(jié)點的狀態(tài)數(shù)是O(m)的，狀態(tài)轉(zhuǎn)移的復(fù)雜度是 ，所以每層的復(fù)雜度是 。 總共有n層，所以狀態(tài)轉(zhuǎn)移的時間復(fù)雜度是 。,回顧,對收費規(guī)則進(jìn)行轉(zhuǎn)化 對時間復(fù)雜度進(jìn)行均攤分析 第二點在樹型動態(tài)規(guī)劃中有著廣泛的運用，本題通過粗略的分析會超時，但是仔細(xì)分析之后，發(fā)現(xiàn)時間復(fù)雜度比粗略的分析少了一維,總結(jié),這2個例題從不同方面闡述了樹型動態(tài)規(guī)劃的解題方法，如： 多維動態(tài)規(guī)劃 兄弟結(jié)點之間通過類似背包的思想進(jìn)行第二次動態(tài)規(guī)劃 對復(fù)雜度的均攤分析 這些方法在比賽中有著廣泛的運用,總結(jié)