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