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