用f[i][0]:表示这个节点不去的值，  g[i][0]:表示达到最大值的取法
 f[i][1]:表示这个节点去的值， g[i][1]:表示达到最大值的取法

然后就是 f[i][0]=min(f[j][0],f[j][1])+min(f[k][0],f[k][1])+... ...
               j,k,... ...表示节点i的儿子
        f[i][1]=f[j][0]+f[k][0]+... ...
               j,k,... ...表示节点i的儿子
       求g[i][0],g[i][1]也是类似的,很简单。

我是递归的实现的，
哪位兄弟放个更好的实现出来吧，感觉递归实现虽然思路很清晰，但有些时候还是不能用的。

• 应该是f[i][0]=max(f[j][0],f[j][1])+max(f[k][0],f[k][1]).....吧？ (570) alpc16 2007-08-15 11:45:46
  • Re:应该是f[i][0]=max(f[j][0],f[j][1])+max(f[k][0],f[k][1]).....吧？ (660) Thank_you 2007-08-15 12:27:14
    • 如果这样的话，那求f[i][0]的时候就不是简单最大值相加了，若碰上相等的情况则两者都要加上吧？ (78) alpc16 2007-08-15 12:32:40
      • 终于AC了，实际上还是只要加一个的。。。。 (55) alpc16 2007-08-15 15:51:27