算法合集之“約制、放寬”方法在解題中的應(yīng)用-資料下載頁
2025-10-07 20:29本頁面
【正文】 j / i / k 轉(zhuǎn)移方程 ?② 當 dis(i,j) D(i)時 , ? (2)當 i=j時 , i的兒子的選擇情況與⑴ 一樣。此時還要加上 建 j上的消防站的費用。 返回 ????的兒子為 ikjkkji FB e s tjWF },m in {)( , i(i=j) / k 轉(zhuǎn)移方程 ?② 當 dis(i,j) D(i)時 , ? (3)當 j不等于 i并且在 i的子樹內(nèi)時 , 此時 j必存在于以 i的某個兒子 child為根的子樹里 返回 ?????c h i l dkikjkkjc h i l dji FB e s tFF并且的兒子為},m in { ,如果 i的兒子 k不等于 child,則 其選擇情況與⑴中一樣 child根據(jù)新添的限制它只能選擇 j上的消防站作為負責站 i \ child \ j i \ il \ j / k child 時間復(fù)雜度分析 ?對于每一個確定的 j,計算 Fi,j需要Ｏ (i的兒子數(shù) )的時間 ,所以計算 F1, j、 F2, j…… F n, j 總共需要O(總兒子數(shù) )=O(n)的時間。 ?因此，總的時間復(fù)雜度為 )( 2nO一張一弛 ? 在保證能找到答案的前提下，對過于寬松而茫無頭緒的條件、限制進行約制 。對于過于嚴格而阻撓前進的條件、限制進行放寬。 一張一弛不僅是文武之道，也是解題之道。 ?能應(yīng)用“約制”方法的題目 : POI2021《 knights》 CEOI《 鋸木廠 》 《 高斯消元解多元一次方程 》 …… ?能應(yīng)用“放寬”方法的題目： WC2021《 友好的動物 》 …… ?更多精彩內(nèi)容在 “約制、放寬”方法在解題中的應(yīng)用 .doc
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1