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

2016-09-28 21:02:30 +08:00
 masterjason

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

1948 次点击
所在节点    问与答
16 条回复
WinterWu
2016-09-28 22:07:48 +08:00
1. 先把问题理顺了
2. 再把问题排版好
iEverX
2016-09-28 23:26:58 +08:00
wap 的算法题啊
iEverX
2016-09-28 23:27:38 +08:00
如果是，那么不是树，是图吧
masterjason
2016-09-28 23:29:43 +08:00
@iEverX 就是树啊其实，说是说图
masterjason
2016-09-28 23:30:04 +08:00
@WinterWu 我排版的时候打了回车的啊，不晓得怎么没了
iEverX
2016-09-28 23:32:25 +08:00
@masterjason 嗯， 又看了一遍，确实是树。。
masterjason
2016-09-28 23:33:40 +08:00
@iEverX 有啥思路么。。。这个树状 dp 的话转移方程也太难写了
iEverX
2016-09-28 23:37:34 +08:00
@masterjason 没有，不过这是一个二叉树
masterjason
2016-09-28 23:43:43 +08:00
@iEverX 为啥是二叉啊，最多三个门呢，你直接算有一个连到父节点了吗
iEverX
2016-09-28 23:49:05 +08:00
@masterjason 是啊，三叉的话就是 4 个门了
zhy0216
2016-09-29 05:49:14 +08:00
这 m 个节点要连接在一起的么?
masterjason
2016-09-29 09:41:03 +08:00
@zhy0216 不用啊，就是你选了一个点和他相临的点也默认选中
masterjason
2016-09-29 11:05:42 +08:00
@iEverX 早上起来又想了下还是没有思路，应该是用动规的吧
iEverX
2016-09-29 13:11:20 +08:00
@masterjason 用动态规划写了，开了个三维数组。记忆的话，只需要保留两层就行了
masterjason
2016-09-29 13:32:11 +08:00
@iEverX ac 了么，第一题的那些小方块会重复的么
iEverX
2016-09-30 13:56:38 +08:00
@masterjason 没试。。第一题不是说只有这么多的小方块，每个用一次

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/309617

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX