動(dòng)態(tài)5樹型-皇宮看守

分析：在下面用根結(jié)點(diǎn)的標(biāo)號(hào)來表示一棵樹，樹T就是根結(jié)點(diǎn)標(biāo)號(hào)為T的樹設(shè)f0[T]表示對(duì)于一棵樹T，不在T的樹根上布置守衛(wèi)的情況下，設(shè)f1[t]表示對(duì)于一棵樹T，不在T的樹根上布置守衛(wèi)的情況下，除了T的根結(jié)點(diǎn)以外的其他全部節(jié)點(diǎn)所需的最少的費(fèi)用，當(dāng)然也可以住T的設(shè)f2[t]表示對(duì)于一棵樹T，在T的樹根上布置守衛(wèi)的情況下，T的假設(shè)T的兒子節(jié)點(diǎn)為T1,T2,…,Tn；則可以得到方程f0[t]1kn

min{f

],f

]}f2[tk

nf1[t]

f0[ti],f2[ti nf2[t]i

f0[t],f1[t],f2[t]} 如果T的根不布置守衛(wèi)，并且要求T的所有結(jié)點(diǎn)，則必須保證T的子結(jié)點(diǎn)中有一如果T的根不布置守衛(wèi)，并且要求除了T的根結(jié)點(diǎn)以外的其他全部節(jié)點(diǎn)，則必須保證T的所有的子結(jié)點(diǎn)Ti都被，而不用管Ti的根上是否有守衛(wèi)。于是每個(gè)子節(jié)點(diǎn)Ti取最優(yōu)的方案min{f(Ti,0),f(Ti,2)}。這樣就得到了（2）式；請(qǐng)注意，有可能f(T,0)=f(T,1)，因?yàn)閒(T,1)只是要求除了T的根結(jié)點(diǎn)以外的其他全部節(jié)點(diǎn)，也就是可以選擇不T的根，價(jià)，這時(shí)候f(T,1)=f(T,0)；有被，則可以被T的根上布置的那個(gè)守衛(wèi)。因此Ti選擇最優(yōu)的方案min{f(Ti,0),f(Ti,1),f(Ti,2)}。這樣就得到了（3）式,ω(T)T上布置守衛(wèi)的以知道f(Ti,1)<=f(Ti,0)。 注意，這里做了一點(diǎn)特殊規(guī)定，因?yàn)楦鶕?jù)前面對(duì)f(T,0)f(T,1)f(T,2)的定義可以知道，在T是葉子的情況下不在T的樹根上布置守衛(wèi)的情況下而要T的全部節(jié)點(diǎn)使不可說明在T是葉子的情況下，不在T的樹根上布置守衛(wèi)的情況下并除了T的根結(jié)點(diǎn)以外的其他全部節(jié)點(diǎn)，最節(jié)約的辦法是不布置任何的守衛(wèi)，這樣代價(jià)最少為0；（6）說明在T注意對(duì)于結(jié)點(diǎn)i只有它的孩子全部求出f0,f1,f2才能求出它本身。也可以采用迭代算法：每次找孩子全部求過的結(jié)點(diǎn)求他的值f0,f1,f2，結(jié)點(diǎn)記錄 記錄每個(gè)結(jié)點(diǎn)的孩子，使用空間大，但在找孩子時(shí)直接用，節(jié)Fori:=1tonForj:=1toa[i].sondo 不記錄結(jié)點(diǎn)的孩子，節(jié)約空間，但在找結(jié)點(diǎn)i的孩子時(shí)，要逐Fori:=1tondoForj:=1tondo Father[j]=Ithen選擇那種方法：根據(jù)題目要求而定3、在 f0[t]時(shí)，可以將（1）化