这是一个创建于 3370 天前的主题，其中的信息可能已经有所发展或是发生改变。
有一颗 n 节点的最多三叉的树，最多有 1000 个节点。 现在我要取其中的 m 个节点， m 不超过 100 想要的是取得所有点和与所有点相邻的点的和要最大 有点没有思路啊，求解。
第 1 条附言 2016-09-28 23:36:21 +08:00
看了一下确实排版的不是特别好，这个题因为涉及到容斥所以 dp 还得带记忆，非常苦恼
 | 1 WinterWu 2016-09-28 22:07:48 +08:00 1. 先把问题理顺了 2. 再把问题排版好 |
 | 2 iEverX 2016-09-28 23:26:58 +08:00 wap 的算法题啊 |
| 3 iEverX 2016-09-28 23:27:38 +08:00 如果是，那么不是树，是图吧 |
 | 4 masterjason OP @iEverX 就是树啊其实，说是说图 |
| 5 masterjason OP @WinterWu 我排版的时候打了回车的啊，不晓得怎么没了 |
| 6 iEverX 2016-09-28 23:32:25 +08:00 @masterjason 嗯， 又看了一遍，确实是树。。 |
| 7 masterjason OP @iEverX 有啥思路么。。。这个树状 dp 的话转移方程也太难写了 |
| 8 iEverX 2016-09-28 23:37:34 +08:00 @masterjason 没有，不过这是一个二叉树 |
| 9 masterjason OP @iEverX 为啥是二叉啊，最多三个门呢，你直接算有一个连到父节点了吗 |
| 10 iEverX 2016-09-28 23:49:05 +08:00 @masterjason 是啊，三叉的话就是 4 个门了 |
 | 11 zhy0216 2016-09-29 05:49:14 +08:00 这 m 个节点要连接在一起的么? |
| 12 masterjason OP @zhy0216 不用啊，就是你选了一个点和他相临的点也默认选中 |
| 13 masterjason OP @iEverX 早上起来又想了下还是没有思路，应该是用动规的吧 |
| 14 iEverX 2016-09-29 13:11:20 +08:00 @masterjason 用动态规划写了，开了个三维数组。记忆的话，只需要保留两层就行了 |
| 15 masterjason OP @iEverX ac 了么，第一题的那些小方块会重复的么 |
| 16 iEverX 2016-09-30 13:56:38 +08:00 @masterjason 没试。。第一题不是说只有这么多的小方块，每个用一次 |
Select Language