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

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