題目大意 給你個(gè)點(diǎn)建立的時(shí)間徐裸，然后給你條邊俺夕，之后有個(gè)詢問题造，每次詢問在某一天圖中兩個(gè)點(diǎn)之間的最短距離恶复。 題目鏈接 Luogu P1119 思路 這...

思路 這個(gè)題目其實(shí)只要把 0 1背包中的每個(gè)物品的價(jià)值改成每個(gè)物品的重量就可以了毁嗦。 總結(jié) 我們?cè)谶M(jìn)行動(dòng)態(tài)規(guī)劃的時(shí)候假如要涉及某個(gè)變量告喊，如這個(gè)題目...

思路 我們?cè)O(shè)為在區(qū)間內(nèi)的答案闪檬，這個(gè)答案從內(nèi)個(gè)小區(qū)間轉(zhuǎn)移而來。那么轉(zhuǎn)移方程就是 要注意的地方 區(qū)間類型有關(guān)動(dòng)態(tài)規(guī)劃的問題一般可以用區(qū)間DP合并來解...