有一颗 n 节点的最多三叉的树，最多有 1000 个节点。 现在我要取其中的 m 个节点， m 不超过 100 想要的是取得所有点和与所有点相邻的点的和要最大 有点没有思路啊，求解。
This topic created in 3539 days ago, the information mentioned may be changed or developed.
Supplement 1 · Sep 28, 2016
看了一下确实排版的不是特别好，这个题因为涉及到容斥所以 dp 还得带记忆，非常苦恼
 |
1
WinterWu Sep 28, 2016
1. 先把问题理顺了
2. 再把问题排版好 |
 |
2
iEverX Sep 28, 2016
wap 的算法题啊
|
|
3
iEverX Sep 28, 2016
如果是，那么不是树，是图吧
|
 |
4
masterjason OP @iEverX 就是树啊其实，说是说图
|
|
5
masterjason OP @WinterWu 我排版的时候打了回车的啊，不晓得怎么没了
|
|
6
iEverX Sep 28, 2016
@masterjason 嗯， 又看了一遍，确实是树。。
|
|
7
masterjason OP @iEverX 有啥思路么。。。这个树状 dp 的话转移方程也太难写了
|
|
8
iEverX Sep 28, 2016
@masterjason 没有，不过这是一个二叉树
|
|
9
masterjason OP @iEverX 为啥是二叉啊，最多三个门呢，你直接算有一个连到父节点了吗
|
|
10
iEverX Sep 28, 2016
@masterjason 是啊，三叉的话就是 4 个门了
|
 |
11
zhy0216 Sep 29, 2016
这 m 个节点要连接在一起的么?
|
|
12
masterjason OP @zhy0216 不用啊，就是你选了一个点和他相临的点也默认选中
|
|
13
masterjason OP @iEverX 早上起来又想了下还是没有思路，应该是用动规的吧
|
|
14
iEverX Sep 29, 2016
@masterjason 用动态规划写了，开了个三维数组。记忆的话，只需要保留两层就行了
|
|
15
masterjason OP @iEverX ac 了么，第一题的那些小方块会重复的么
|
|
16
iEverX Sep 30, 2016
@masterjason 没试。。第一题不是说只有这么多的小方块，每个用一次
|
Select Language