V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
masterjason
V2EX  ›  问与答

问一个不晓得该不该用树形 dp 的算法题

  •  
  •   masterjason · 2016-09-28 21:02:30 +08:00 · 1545 次点击
    这是一个创建于 1893 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有一颗 n 节点的最多三叉的树,最多有 1000 个节点。 现在我要取其中的 m 个节点, m 不超过 100 想要的是取得所有点和与所有点相邻的点的和要最大 有点没有思路啊,求解。

    第 1 条附言  ·  2016-09-28 23:36:21 +08:00
    看了一下确实排版的不是特别好,这个题因为涉及到容斥所以 dp 还得带记忆,非常苦恼
    16 条回复    2016-09-30 13:56:38 +08:00
    WinterWu
        1
    WinterWu  
       2016-09-28 22:07:48 +08:00
    1. 先把问题理顺了
    2. 再把问题排版好
    iEverX
        2
    iEverX  
       2016-09-28 23:26:58 +08:00
    wap 的算法题啊
    iEverX
        3
    iEverX  
       2016-09-28 23:27:38 +08:00
    如果是,那么不是树,是图吧
    masterjason
        4
    masterjason  
    OP
       2016-09-28 23:29:43 +08:00
    @iEverX 就是树啊其实,说是说图
    masterjason
        5
    masterjason  
    OP
       2016-09-28 23:30:04 +08:00
    @WinterWu 我排版的时候打了回车的啊,不晓得怎么没了
    iEverX
        6
    iEverX  
       2016-09-28 23:32:25 +08:00
    @masterjason 嗯, 又看了一遍,确实是树。。
    masterjason
        7
    masterjason  
    OP
       2016-09-28 23:33:40 +08:00
    @iEverX 有啥思路么。。。这个树状 dp 的话转移方程也太难写了
    iEverX
        8
    iEverX  
       2016-09-28 23:37:34 +08:00
    @masterjason 没有,不过这是一个二叉树
    masterjason
        9
    masterjason  
    OP
       2016-09-28 23:43:43 +08:00
    @iEverX 为啥是二叉啊,最多三个门呢,你直接算有一个连到父节点了吗
    iEverX
        10
    iEverX  
       2016-09-28 23:49:05 +08:00
    @masterjason 是啊,三叉的话就是 4 个门了
    zhy0216
        11
    zhy0216  
       2016-09-29 05:49:14 +08:00
    这 m 个节点要连接在一起的么?
    masterjason
        12
    masterjason  
    OP
       2016-09-29 09:41:03 +08:00 via iPhone
    @zhy0216 不用啊,就是你选了一个点和他相临的点也默认选中
    masterjason
        13
    masterjason  
    OP
       2016-09-29 11:05:42 +08:00
    @iEverX 早上起来又想了下还是没有思路,应该是用动规的吧
    iEverX
        14
    iEverX  
       2016-09-29 13:11:20 +08:00
    @masterjason 用动态规划写了,开了个三维数组。记忆的话,只需要保留两层就行了
    masterjason
        15
    masterjason  
    OP
       2016-09-29 13:32:11 +08:00
    @iEverX ac 了么,第一题的那些小方块会重复的么
    iEverX
        16
    iEverX  
       2016-09-30 13:56:38 +08:00
    @masterjason 没试。。第一题不是说只有这么多的小方块,每个用一次
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1405 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 17:44 · PVG 01:44 · LAX 09:44 · JFK 12:44
    ♥ Do have faith in what you're doing.