消防站解題報(bào)告-資料下載頁
2025-03-25 05:39本頁面
【正文】 為根的子樹中，修建合符要求(子樹中所有結(jié)點(diǎn)到其樹內(nèi)的負(fù)責(zé)站的距離不超過其對(duì)應(yīng)的函數(shù)D值)的消防站的最小費(fèi)用。明顯地下面對(duì)進(jìn)行分析：①當(dāng)時(shí)，∞，這表示不存在狀態(tài)；②當(dāng)時(shí)，⑴當(dāng)在以為根的子樹外時(shí)，對(duì)于的每個(gè)兒子都有兩種選擇：選擇以為根的子樹內(nèi)或外的消防站為負(fù)責(zé)站。當(dāng)選擇以為根的子樹內(nèi)的消防站為負(fù)責(zé)站時(shí)，其子樹所需的最少費(fèi)用為，當(dāng)選擇以為根的子樹外的消防站為負(fù)責(zé)站時(shí)，根據(jù)新添的限制易知只可以選擇上的消防站作為負(fù)責(zé)站，此時(shí)其子樹所需的最少費(fèi)用為。綜上得到⑵當(dāng)時(shí)，的每個(gè)兒子的選擇情況與⑴中的一樣。此時(shí)還要加上修建上的消防站的費(fèi)用。因此⑶當(dāng)并且在以為根的子樹內(nèi)時(shí)，此時(shí)必定在的某個(gè)兒子的子樹里。對(duì)于的每個(gè)不是的兒子其選擇情況與⑴中的一樣，而對(duì)于，根據(jù)新添的限制它只能選擇作為負(fù)責(zé)站。綜上得到復(fù)雜度分析：時(shí)間復(fù)雜度為,空間復(fù)雜度為。【小結(jié)】“放寬”方法和“約制”方法不總是互相排斥、矛盾的，它們往往會(huì)互相補(bǔ)充。它們各自可以在需要它們的方面發(fā)揮特長——應(yīng)用“放寬”方法確定狀態(tài)。應(yīng)用“約制”方法確定狀態(tài)轉(zhuǎn)移方程。在保證能找到答案的前提下，對(duì)于過于嚴(yán)格而阻撓前進(jìn)的條件、限制，我們對(duì)它進(jìn)行“放寬”；對(duì)于過于寬松而茫無頭緒的條件、限制，我們對(duì)它進(jìn)行“約制”——這就是所謂的一張一弛了。一張一弛不僅是文武之道，更是解題之道。5 / 5
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1