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

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

IOI05河流

NOI06網(wǎng)絡(luò)收費(fèi)

POI04山洞

第五頁，共三十一頁，編輯于2023年，星期三問題描述n個(gè)伐木的村莊在0號(hào)結(jié)點(diǎn)有一個(gè)巨大的伐木場(chǎng)，木料被砍下后，順著河流而被運(yùn)到0號(hào)結(jié)點(diǎn)的伐木場(chǎng)為了減少運(yùn)輸木料的費(fèi)用，再額外建造k個(gè)伐木場(chǎng)這些伐木場(chǎng)建造后，木料可以在運(yùn)輸過程中第一個(gè)碰到的新伐木場(chǎng)被處理。第六頁，共三十一頁，編輯于2023年，星期三問題描述所有的河流都不會(huì)分叉，也就是說，每一個(gè)村子，順流而下都只有一條路到0號(hào)結(jié)點(diǎn)。已知每個(gè)村子每年要產(chǎn)多少木料，求在哪些村子建設(shè)伐木場(chǎng)能獲得最小的運(yùn)費(fèi)。N≤100K≤50第七頁，共三十一頁，編輯于2023年，星期三問題抽象本題的題意很明確，即建立k個(gè)伐木廠，使得把所有木材運(yùn)送到最近的祖先伐木廠的費(fèi)用最小。由于題目給定的是一棵樹，數(shù)據(jù)規(guī)模又比較大，很容易聯(lián)想到樹型動(dòng)態(tài)規(guī)劃。第八頁，共三十一頁，編輯于2023年，星期三狀態(tài)的確立首先必須有的是當(dāng)前點(diǎn)及以當(dāng)前點(diǎn)為根的子樹中，一共建立了多少伐木廠，但是這顯然是不夠的，因?yàn)檫@個(gè)狀態(tài)中沒有任何與伐木廠位置相關(guān)的信息。因此我們還需要再加一維。加上有關(guān)伐木廠的位置的信息。表示把以from為根的子樹中建立kleft個(gè)伐木廠，把木材全部運(yùn)送到最近的祖先伐木廠，所需要的費(fèi)用，并且from有一個(gè)祖先伐木廠為to_。（注意到這里to_僅僅是from的祖先伐木廠，而未必是from的最近祖先伐木廠，這是為什么呢？）第九頁，共三十一頁，編輯于2023年，星期三狀態(tài)的轉(zhuǎn)移狀態(tài)轉(zhuǎn)移分2種情況討論：在from建立伐木廠不在from建立伐木廠第十頁，共三十一頁，編輯于2023年，星期三狀態(tài)的轉(zhuǎn)移在from建立伐木廠：即分配kleft個(gè)伐木廠給from的子結(jié)點(diǎn)，使得費(fèi)用最小。這分配的過程，也就相當(dāng)于背包問題。

h1是用來解背包問題的臨時(shí)數(shù)組，son是from的兒子結(jié)點(diǎn)。第十一頁，共三十一頁，編輯于2023年，星期三狀態(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)。第十二頁，共三十一頁，編輯于2023年，星期三狀態(tài)的轉(zhuǎn)移最后第十三頁，共三十一頁，編輯于2023年，星期三效率分析由于狀態(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ù)雜度為。第十四頁，共三十一頁，編輯于2023年，星期三回顧本題的動(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)移總量分析總量分析均攤分析第十五頁，共三十一頁，編輯于2023年，星期三例題解析NOI03逃學(xué)的小孩

IOI05河流

NOI06網(wǎng)絡(luò)收費(fèi)

POI04山洞

第十六頁，共三十一頁，編輯于2023年，星期三問題描述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)用之和。第十七頁，共三十一頁，編輯于2023年，星期三問題描述I付費(fèi)方式J付費(fèi)方式nA與nB大小關(guān)系付費(fèi)系數(shù)k實(shí)際付費(fèi)AAnA<nB2k*Fi,jAB1BA1BB0AAnA≥nB0AB1BA1BB2第十八頁，共三十一頁，編輯于2023年，星期三問題描述對(duì)于用戶i，如果他/她想改變付費(fèi)方式（由A改為B或由B改為A），就必須支付Ci元給網(wǎng)絡(luò)公司以修改檔案。給定每個(gè)用戶注冊(cè)時(shí)所選擇的付費(fèi)方式以及Ci，試求這些用戶應(yīng)該如何選擇自己的付費(fèi)方式以使得總費(fèi)用最少（更改付費(fèi)方式費(fèi)用+配對(duì)收費(fèi)的費(fèi)用）。

N≤10第十九頁，共三十一頁，編輯于2023年，星期三問題轉(zhuǎn)化配對(duì)收費(fèi)的規(guī)則B較多時(shí)，AA收費(fèi)系數(shù)為2AB收費(fèi)系數(shù)為1BB收費(fèi)系數(shù)為0其他情況反之設(shè)想：B較多時(shí)，在每一個(gè)A結(jié)點(diǎn)上有1個(gè)收費(fèi)系數(shù)否則在每一個(gè)B結(jié)點(diǎn)上有1個(gè)收費(fèi)系數(shù)單點(diǎn)收費(fèi)第二十頁，共三十一頁，編輯于2023年，星期三狀態(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)。因此，這也是需要記錄的。點(diǎn)i所管轄的所有用戶中，有j個(gè)用戶為A，在i的每個(gè)祖先u上，如果na<nb，則標(biāo)0，否則標(biāo)1，這個(gè)數(shù)列可以用二進(jìn)制表示，用k記錄，在這種情況下的最少花費(fèi)。第二十一頁，共三十一頁，編輯于2023年，星期三狀態(tài)的轉(zhuǎn)移狀態(tài)轉(zhuǎn)移方程，其實(shí)就是將j個(gè)用戶分配給i的左右子節(jié)點(diǎn)，并更改k第二十二頁，共三十一頁，編輯于2023年，星期三狀態(tài)的轉(zhuǎn)移當(dāng)i是葉節(jié)點(diǎn)時(shí)，可以根據(jù)k算出i與其它用戶配對(duì)收費(fèi)時(shí)所要交的費(fèi)用，再根據(jù)i的初始情況加上AB的轉(zhuǎn)化費(fèi)用。第二十三頁，共三十一頁，編輯于2023年，星期三效率分析粗略看來，空間復(fù)雜度是，時(shí)間復(fù)雜度是，對(duì)于本題的數(shù)據(jù)可以同時(shí)超空間和超時(shí)間了。不過這只是很粗略的分析，這些狀態(tài)中有很多是取不到的。

第二十四頁，共三十一頁，編輯于2023年，星期三效率分析把根節(jié)點(diǎn)看做第0層，葉節(jié)點(diǎn)就是第n層，對(duì)于任意的第i層，A用戶的個(gè)數(shù)最多只有，而祖先結(jié)點(diǎn)只有i個(gè)，即k最大只有，把的后兩維合并成一維，空間復(fù)雜度其實(shí)只有。第二十五頁，共三十一頁，編輯于2023年，星期三效率分析再看時(shí)間復(fù)雜度，對(duì)于第i層，有個(gè)結(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的狀態(tài)數(shù)是O(m)的，狀態(tài)轉(zhuǎn)移的復(fù)雜度是，所以每層的復(fù)雜度是。總共有n層，所以狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度是。第二十六頁，共三十一頁，編輯于2023年，星期三回顧對(duì)收費(fèi)規(guī)則進(jìn)行轉(zhuǎn)化對(duì)時(shí)間復(fù)雜度進(jìn)行均攤分析第二點(diǎn)在樹型動(dòng)態(tài)規(guī)劃中有著廣泛的運(yùn)用，本題通過粗略的分析會(huì)超時(shí)，但是仔細(xì)分析之后，發(fā)現(xiàn)時(shí)間復(fù)雜度比粗略的分析少了一維第二十七頁，共三十一頁，編輯于2023年，星期三總結(jié)

這2個(gè)例題從不同方面闡述了樹型動(dòng)態(tài)規(guī)劃的解題方法，如：多維動(dòng)態(tài)規(guī)劃兄弟結(jié)點(diǎn)之間通過類似背包的思想進(jìn)行第二次動(dòng)態(tài)規(guī)劃對(duì)復(fù)雜度的均攤分析這些方法在比賽中有著廣泛的運(yùn)用第二十八頁，共三十一頁，編輯于2023年，星期三總結(jié)在此過程中，我認(rèn)識(shí)到：面對(duì)