※ 引述《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