一、簡(jiǎn)介

有一類(lèi)問(wèn)題，它可以采用 DP 解決。但是，如果我們加入區(qū)間查詢(xún)，單點(diǎn)修改甚至區(qū)間修改，普通DP望塵莫及。于是，動(dòng)態(tài)DP就應(yīng)運(yùn)而生了。

二、例題

例題一：給定一個(gè)長(zhǎng)度為 n 的序列，你需要維護(hù)兩種操作：

①查詢(xún)一個(gè)區(qū)間的最大子段和；

②單點(diǎn)修改(即將一個(gè)位置上的數(shù)改成另一個(gè)數(shù))

Solution

首先，考慮這樣一道題目：求出整個(gè)序列的最大子段和，沒(méi)有修改。

令表示以 i 為結(jié)尾的區(qū)間的最大和，則不難得到狀態(tài)轉(zhuǎn)移：

令表示 [1,i] 的最大子段和，不難得到

邊界：

答案：

加入了單點(diǎn)修改以及區(qū)間查詢(xún)之后，我們?cè)撛趺崔k呢？

觀(guān)察一下我們的狀態(tài)轉(zhuǎn)移，可以發(fā)現(xiàn)——從轉(zhuǎn)移到的轉(zhuǎn)移式，僅僅與有關(guān)。這啟發(fā)我們?nèi)ソo每個(gè)位置設(shè)定一個(gè)矩陣，并通過(guò)矩陣乘法來(lái)表示 f 的轉(zhuǎn)移。

但是，轉(zhuǎn)移式中含有max，不符合普通矩陣乘法的形式。不慌！我們可以大膽地重定義矩陣乘法 A ? B = C：

從而，我們就寫(xiě)出了 f 的轉(zhuǎn)移與 i 之間的關(guān)系：

這樣只能求出 f，而并不能求出我們所真正需要的 m 。所以，我們?cè)诰仃囍性偌尤胍恍幸涣衼?lái)表示 m 的轉(zhuǎn)移與f，i 的關(guān)系。

從而，我們得到了最終的式子：

對(duì)于一次形如 [L,R] 的查詢(xún)，我們初始化，然后依次將乘上 L , L+1 , ? ? , R 處的矩陣即可。

暴力乘顯然超時(shí)，考慮優(yōu)化。注意到這個(gè)矩陣乘法是有結(jié)合率的，于是我們采用線(xiàn)段樹(shù)來(lái)維護(hù)區(qū)間矩陣積，查詢(xún)的時(shí)候直接用向量依次乘上 O(logn) 個(gè)矩陣即可。

對(duì)于一次單點(diǎn)修改，它只會(huì)導(dǎo)致一個(gè)矩陣的改變，于是在線(xiàn)段樹(shù)上執(zhí)行一次單點(diǎn)修改即可。

時(shí)間復(fù)雜度

例題二：給定一棵大小為 n 的樹(shù)，每個(gè)節(jié)點(diǎn)有一個(gè)點(diǎn)權(quán)；q 次操作，每次單點(diǎn)修改或查詢(xún)整棵樹(shù)的最大獨(dú)立集。

Solution

剛才我們所討論的例 1 是序列上的問(wèn)題?，F(xiàn)在我們將它搬到了樹(shù)上，顯然無(wú)法湊效了。

依然先考慮不帶修的情況。

令表示，在 i 子樹(shù)中的最大獨(dú)立子集；表示節(jié)點(diǎn) i 不能選，表示 i 必須選。

狀態(tài)轉(zhuǎn)移:

不難發(fā)現(xiàn)，對(duì)一個(gè)節(jié)點(diǎn)的點(diǎn)權(quán)進(jìn)行改變后，只會(huì)改變它以及它祖先的一些 f 值。但是，這棵樹(shù)可能會(huì)退化成一條鏈，從而使得每次要修改的節(jié)點(diǎn)的數(shù)量很多。

考慮使用樹(shù)鏈剖分來(lái)優(yōu)化這一步驟。

令 i 的重兒子是 ws，，，則不難得到

與序列上的動(dòng)態(tài) dp 類(lèi)似，可以設(shè)計(jì)一個(gè)廣義矩陣乘法來(lái)完成轉(zhuǎn)移：

若修改了 i 的點(diǎn)權(quán)，我們先在 i 處做單點(diǎn)修改，并不停地往上跳重鏈，通過(guò)線(xiàn)段樹(shù)求出當(dāng)前重鏈的矩陣乘積；同時(shí)，也要記得在跳到的鏈頂?shù)母赣H處做單點(diǎn)修改。

時(shí)間復(fù)雜度