※ 引述《denehs (DE)》之銘言：
: ※ 引述《CorruptAngel (微笑面具)》之銘言：
: : ??!
: : 如果共用很多子樹呢@@?
: 我解釋一下我實際coding時的作法
: 對於每一個node,我給他們各兩個值,O代表將這個node拿掉
: 這個node+這個node以下所能貢獻的最大value
: X則是不拿
: 則
: O是他底下一層nodes每個OX取最大,
: X我則是直接設0
: 然後做的順序,隨意找一個node往下做,然後再找一個node(沒做過的)往下做
: 直到做完,如果碰到共用子樹,且共用的子樹已被處理過
: 就直接使用那顆子樹的結果...
: XD~~~忘了把code留下(好像也沒辦法留@@?)
: 真是抱歉,不會用很好的方法解釋@@"....
我實際上跑node的順序是1~n
所以像上面那個側資
1 -2
2 1 1
3 1 1
4 1 1
我ㄧ開始跑1
node 1 O:未知 X:0
(跑到下一層,與node 1有直接connect的node 2,3,4)
node 2 O:1 X:0 (因為下層都沒了,so O就是自己的value)
node 3 O:1 X:0
node 4 O:1 X:0
(回到上一層node 1)
max of node2:1
max of node3:1
max of node4:1
3+value of node 1 = 1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.181